{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Alien Dictionary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #topological-sort #array #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #拓扑排序 #数组 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: alienOrder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #火星词典"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现有一种使用英语字母的火星语言，这门语言的字母顺序对你来说是未知的。</p>\n",
    "\n",
    "<p>给你一个来自这种外星语言字典的字符串列表 <code>words</code> ，<code>words</code> 中的字符串已经 <strong>按这门新语言的字母顺序进行了排序</strong> 。</p>\n",
    "\n",
    "<p>如果这种说法是错误的，并且给出的 <code>words</code> 不能对应任何字母的顺序，则返回 <code>\"\"</code> 。</p>\n",
    "\n",
    "<p>否则，返回一个按新语言规则的&nbsp;<strong>字典递增顺序 </strong>排序的独特字符串。如果有多个解决方案，则返回其中 <strong>任意一个</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"wrt\",\"wrf\",\"er\",\"ett\",\"rftt\"]\n",
    "<strong>输出：</strong>\"wertf\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"z\",\"x\"]\n",
    "<strong>输出：</strong>\"zx\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"z\",\"x\",\"z\"]\n",
    "<strong>输出：</strong>\"\"\n",
    "<strong>解释：</strong>不存在合法字母顺序，因此返回 <code>\"\" 。</code>\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 100</code></li>\n",
    "\t<li><code>words[i]</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [alien-dictionary](https://leetcode.cn/problems/alien-dictionary/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [alien-dictionary](https://leetcode.cn/problems/alien-dictionary/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"wrt\",\"wrf\",\"er\",\"ett\",\"rftt\"]', '[\"z\",\"x\"]', '[\"z\",\"x\",\"z\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from dataclasses import dataclass\n",
    "from typing import Dict, List, Optional, Set\n",
    "\n",
    "@dataclass\n",
    "class Edge:\n",
    "    source: str\n",
    "    dest:  str\n",
    "\n",
    "Node = str\n",
    "AdjList = Dict[Node, Set[Node]]\n",
    "\n",
    "class Solution:\n",
    "    def find_unique_letters(self, words: List[str]) -> List[str]:\n",
    "        self.unique_letters = set(\"\".join(words))\n",
    "\n",
    "\n",
    "    def build_edge(self, word1: str, word2: str) -> Optional[Edge]:\n",
    "        for a, b in zip(word1, word2):\n",
    "            if a != b:\n",
    "                return Edge(a, b)\n",
    "\n",
    "        return None\n",
    "\n",
    "\n",
    "    def build_graph(self, words: List[str]) -> (bool, AdjList, AdjList):\n",
    "        enter: AdjList = {c: set() for c in self.unique_letters}\n",
    "        leave: AdjList = {c: set() for c in self.unique_letters}\n",
    "\n",
    "        for i in range(len(words) - 1):\n",
    "            if words[i + 1] == words[i][:len(words[i + 1])]:\n",
    "                return (False, {}, {})\n",
    "\n",
    "            edge = self.build_edge(words[i], words[i + 1])\n",
    "            if edge is not None:\n",
    "                leave[edge.source].add(edge.dest)\n",
    "                enter[edge.dest].add(edge.source)\n",
    "\n",
    "        return (True, enter, leave)\n",
    "\n",
    "\n",
    "    def topological_sort(self, enter: AdjList, leave: AdjList) -> str:\n",
    "        if len(enter) == 1:\n",
    "            return enter.keys()[0]\n",
    "\n",
    "        sources: Set[Node] = set()\n",
    "        next_sources: Set[Node] = set(\n",
    "            node for node in enter if len(enter[node]) == 0\n",
    "        )\n",
    "\n",
    "        result: List[str] = []\n",
    "        while len(next_sources) > 0:\n",
    "            sources, next_sources = next_sources, sources\n",
    "            result.extend(sources)\n",
    "            \n",
    "            for source in sources:\n",
    "                for dest in leave[source]:\n",
    "                    enter[dest].discard(source)\n",
    "                    if len(enter[dest]) == 0:\n",
    "                        next_sources.add(dest)\n",
    "\n",
    "            sources.clear()\n",
    "        \n",
    "        return \"\".join(result)\n",
    "\n",
    "\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        if len(words) == 0:\n",
    "            return \"\"\n",
    "\n",
    "        unique_words: List[str] = [words[0]]\n",
    "        for i in range(1, len(words)):\n",
    "            if words[i] != unique_words[-1]:\n",
    "                unique_words.append(words[i])\n",
    "\n",
    "        self.find_unique_letters(unique_words)\n",
    "\n",
    "        enter: AdjList = {}\n",
    "        leave: AdjList = {}\n",
    "        valid, enter, leave = self.build_graph(unique_words)\n",
    "        if not valid:\n",
    "            return \"\"\n",
    "        if all(len(neighbors) == 0 for neighbors in leave.values()):\n",
    "            return \"\".join(self.unique_letters)\n",
    "\n",
    "        order = self.topological_sort(enter, leave)\n",
    "\n",
    "        return \"\" if len(self.unique_letters) != len(order) else order"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "\n",
    "        indegree =  defaultdict(int)\n",
    "        releation = defaultdict(list)\n",
    "        total_node = set()\n",
    "        for i in words:\n",
    "            total_node.update(set(i))\n",
    "        for i in range(1, len(words)):\n",
    "            for j, k in zip(words[i -1], words[i]):\n",
    "                if j != k:\n",
    "                    if k not in releation[j]:\n",
    "                        indegree[k] += 1\n",
    "                        releation[j].append(k)\n",
    "                    break\n",
    "            else:\n",
    "                if len(words[i - 1]) > len(words[i]) and words[i] in words[i - 1]:\n",
    "                    return \"\"\n",
    "        zero = [x for x in total_node if x not in indegree]\n",
    "        res = \"\"\n",
    "        while zero:\n",
    "            t =  zero.pop()\n",
    "            res += t\n",
    "            for i in releation.get(t, []):\n",
    "                indegree[i] -= 1\n",
    "                if indegree[i] == 0:\n",
    "                    zero.append(i)\n",
    "        if len(res) == len(total_node):\n",
    "            return res\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "\n",
    "        graph = {}\n",
    "\n",
    "        indegree = {}\n",
    "\n",
    "        for c in words[0]:\n",
    "            indegree[c] = 0\n",
    "        \n",
    "        for i in range(len(words) - 1):\n",
    "            word1 = words[i]\n",
    "            word2 = words[i + 1]\n",
    "\n",
    "            for w2 in word2:\n",
    "                if w2 not in indegree:\n",
    "                    indegree[w2] = 0\n",
    "\n",
    "            for w1, w2 in zip(word1, word2):\n",
    "                if w1 != w2:\n",
    "                    if w1 not in graph:\n",
    "                        graph[w1] = [w2]\n",
    "                    else:\n",
    "                        graph[w1].append(w2)\n",
    "                \n",
    "                    indegree[w2] += 1\n",
    "                    break\n",
    "            else:\n",
    "                if len(word2) < len(word1):\n",
    "                    return \"\"\n",
    "        \n",
    "        queue = deque()\n",
    "\n",
    "        ans = \"\"\n",
    "\n",
    "        for w, d in indegree.items():\n",
    "            if d == 0:\n",
    "                queue.append(w)\n",
    "        # print(queue)\n",
    "        # print(graph)\n",
    "        # print(indegree)\n",
    "        while queue:\n",
    "            \n",
    "            cur_w = queue.popleft()\n",
    "            ans += cur_w\n",
    "\n",
    "            if cur_w not in graph:\n",
    "                continue\n",
    "            for neighbour in graph[cur_w]:\n",
    "                indegree[neighbour] -= 1\n",
    "                if indegree[neighbour] == 0:\n",
    "                    queue.append(neighbour)\n",
    "        \n",
    "        return ans if len(ans) == len(indegree) else \"\"\n",
    "\n",
    "                    \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        def init_graph():\n",
    "            g, n = defaultdict(set), len(words)\n",
    "            for i in range(n - 1):\n",
    "                word0, word1 = words[i], words[i + 1]\n",
    "                n0, n1 = len(word0), len(word1)\n",
    "                # 形如[\"abc\", \"ab\"]的样例是违反定义的, 特殊判断\n",
    "                if n0 > n1 and word0[:n1] == word1:\n",
    "                    return None\n",
    "                \n",
    "                m = min(n0, n1)\n",
    "                for j in range(m):\n",
    "                    if word0[j] == word1[j]:\n",
    "                        continue\n",
    "                    # 第一对不同的字符提供序关系, 后面的字符忽略\n",
    "                    g[word0[j]].add(word1[j])\n",
    "                    break\n",
    "            return g\n",
    "        \n",
    "        def count_in_degree(g):\n",
    "            degree = {}\n",
    "            # 将出现字符的入度初始化为0\n",
    "            for word in words:\n",
    "                for ch in word:  \n",
    "                    degree[ch] = 0\n",
    "            \n",
    "            for char, charset in g.items():\n",
    "                for ch in charset:\n",
    "                    degree[ch] += 1\n",
    "            return degree\n",
    "        \n",
    "        g = init_graph()\n",
    "        if g is None:\n",
    "            return \"\"\n",
    "        in_degree = count_in_degree(g)\n",
    "        \n",
    "        queue, count = deque(), 0\n",
    "        for char, degree in in_degree.items():\n",
    "            count += 1\n",
    "            if degree == 0:\n",
    "                queue.append(char)\n",
    "            \n",
    "        order = \"\"\n",
    "        while queue:\n",
    "            ch = queue.popleft()\n",
    "            order += ch\n",
    "            \n",
    "            if ch in g:\n",
    "                for c in g[ch]:\n",
    "                    in_degree[c] -= 1\n",
    "                    if in_degree[c] == 0:\n",
    "                        queue.append(c)\n",
    "        return order if len(order) == count else \"\"\n",
    "\n",
    "# 作者：icode\n",
    "# 链接：https://leetcode.cn/problems/alien-dictionary/solutions/1150043/python3gen-ju-ti-yi-que-ding-xu-guan-xi-4pygc/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict,deque\n",
    "from itertools import pairwise\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        g = defaultdict(list)\n",
    "        v_in = defaultdict(int)\n",
    "        for c in words[0]:\n",
    "            if c not in v_in:\n",
    "                v_in.setdefault(c,0)\n",
    "        for a,b in pairwise(words):\n",
    "            for c in b:\n",
    "                if c not in v_in:\n",
    "                    v_in.setdefault(c,0)\n",
    "            flag = 0\n",
    "            for u, v in zip(a,b):\n",
    "                # print(u,v)\n",
    "                if u!=v:\n",
    "                    if v not in g[u]:\n",
    "                        g[u].append(v)\n",
    "                        v_in[v] += 1\n",
    "                        v_in[u] = max(v_in[u],0)\n",
    "                    flag=1\n",
    "                    break\n",
    "            if not flag:\n",
    "                if len(a)>len(b):\n",
    "                    return \"\"\n",
    "        # print(g)\n",
    "        q=deque()\n",
    "        for i in v_in:\n",
    "            if v_in[i]==0:\n",
    "                q.append(i)\n",
    "        ans = []\n",
    "        while q:\n",
    "            # print(v_in,q)\n",
    "            v = q.popleft()\n",
    "            ans.append(v)\n",
    "            for w in g[v]:\n",
    "                v_in[w]-=1\n",
    "                if v_in[w]==0:\n",
    "                    q.append(w)\n",
    "        for i in v_in:\n",
    "            if v_in[i]>0:\n",
    "                return \"\"\n",
    "        return \"\".join(ans)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        # a b c\n",
    "        # a c b\n",
    "        g = defaultdict(list)\n",
    "        indegree = {c: 0 for c in words[0]}\n",
    "\n",
    "        for s, t in pairwise(words):\n",
    "            for c in t:\n",
    "                indegree.setdefault(c, 0)\n",
    "            for u, v in zip(s, t):\n",
    "                if u != v:\n",
    "                    g[u].append(v)\n",
    "                    indegree[v] += 1\n",
    "                    break\n",
    "            else:\n",
    "                if len(s) > len(t):\n",
    "                    return \"\"\n",
    "        queue = deque([u for u, d in indegree.items() if d == 0])\n",
    "\n",
    "        count = 0\n",
    "        order = []\n",
    "        while queue:\n",
    "            front = queue.popleft()\n",
    "            order.append(front)\n",
    "            count += 1\n",
    "            for v in g[front]:\n",
    "                indegree[v] -= 1\n",
    "                if indegree[v] == 0:\n",
    "                    queue.append(v)\n",
    "        if count == len(indegree):\n",
    "            return ''.join(order)\n",
    "        return \"\"\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        graph, s = defaultdict(list), set()\n",
    "        for w in words:\n",
    "            s = s.union(set(w))\n",
    "        d = [0] * 26\n",
    "        for a, b in pairwise(words):\n",
    "            for ca, cb in zip(a, b):\n",
    "                if ca != cb:\n",
    "                    graph[ca].append(cb)\n",
    "                    d[ord(cb) - ord('a')] += 1\n",
    "                    break \n",
    "            else:\n",
    "                if len(a) > len(b):\n",
    "                    return \"\"\n",
    "        start = [k for k in s if d[ord(k) - ord('a')] == 0]\n",
    "        for ch in start:\n",
    "            for nxt in graph[ch]:\n",
    "                d[v := ord(nxt) - ord('a')] -= 1\n",
    "                if not d[v]:\n",
    "                    start.append(nxt)\n",
    "        return \"\".join(start) if len(start) == len(s) else \"\" "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        chars = set()\n",
    "        for w in words:\n",
    "            for c in w:\n",
    "                chars.add(c)\n",
    "        graph = {c: set() for c in chars}\n",
    "        in_degree = {c: 0 for c in chars}\n",
    "\n",
    "        for i in range(len(words) - 1):\n",
    "            w1, w2 = words[i], words[i + 1]\n",
    "            min_len = min(len(w1), len(w2))\n",
    "            if w1[:min_len] == w2[:min_len] and len(w1) > len(w2):\n",
    "                return \"\"\n",
    "            for j in range(min_len):\n",
    "                if w1[j] != w2[j]:\n",
    "                    if w2[j] not in graph[w1[j]]:\n",
    "                        graph[w1[j]].add(w2[j])\n",
    "                        in_degree[w2[j]] += 1\n",
    "                    break\n",
    "\n",
    "        queue = deque()\n",
    "        res = []\n",
    "        for c, deg in in_degree.items():\n",
    "            if deg == 0:\n",
    "                queue.append(c)\n",
    "                \n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            res.append(node)\n",
    "            for nei in graph[node]:\n",
    "                in_degree[nei] -= 1\n",
    "                if in_degree[nei] == 0:\n",
    "                    queue.append(nei)\n",
    "        \n",
    "        if len(res) != len(chars): return \"\"\n",
    "        else: return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "\n",
    "        graph = {}\n",
    "\n",
    "        indegree = {}\n",
    "\n",
    "        for c in words[0]:\n",
    "            indegree[c] = 0\n",
    "        \n",
    "        for i in range(len(words) - 1):\n",
    "            word1 = words[i]\n",
    "            word2 = words[i + 1]\n",
    "\n",
    "            for w2 in word2:\n",
    "                if w2 not in indegree:\n",
    "                    indegree[w2] = 0\n",
    "\n",
    "            for w1, w2 in zip(word1, word2):\n",
    "                if w1 != w2:\n",
    "                    if w1 not in graph:\n",
    "                        graph[w1] = [w2]\n",
    "                    else:\n",
    "                        graph[w1].append(w2)\n",
    "                \n",
    "                    indegree[w2] += 1\n",
    "                    break\n",
    "            else:\n",
    "                if len(word2) < len(word1):\n",
    "                    return \"\"\n",
    "        \n",
    "        queue = deque()\n",
    "\n",
    "        ans = \"\"\n",
    "\n",
    "        for w, d in indegree.items():\n",
    "            if d == 0:\n",
    "                queue.append(w)\n",
    "        # print(queue)\n",
    "        # print(graph)\n",
    "        # print(indegree)\n",
    "        while queue:\n",
    "            \n",
    "            cur_w = queue.popleft()\n",
    "            ans += cur_w\n",
    "\n",
    "            if cur_w not in graph:\n",
    "                continue\n",
    "            for neighbour in graph[cur_w]:\n",
    "                indegree[neighbour] -= 1\n",
    "                if indegree[neighbour] == 0:\n",
    "                    queue.append(neighbour)\n",
    "        \n",
    "        return ans if len(ans) == len(indegree) else \"\"\n",
    "\n",
    "                    \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        g = {}\n",
    "        states = {}\n",
    "        order = []\n",
    "        for c in words[0]:\n",
    "            g[c] = []\n",
    "        for s, t in pairwise(words):\n",
    "            for c in t:\n",
    "                g.setdefault(c, [])\n",
    "            for u, v in zip(s, t):\n",
    "                if u != v:\n",
    "                    g[u].append(v)\n",
    "                    break\n",
    "            else:\n",
    "                if len(s) > len(t):\n",
    "                    return \"\"\n",
    "\n",
    "        VISITING, VISITED = 1, 2\n",
    "        \n",
    "        def dfs(u: str) -> bool:\n",
    "            states[u] = VISITING\n",
    "            for v in g[u]:\n",
    "                if v not in states:\n",
    "                    if not dfs(v):\n",
    "                        return False\n",
    "                elif states[v] == VISITING:\n",
    "                    return False\n",
    "            order.append(u)\n",
    "            states[u] = VISITED\n",
    "            return True\n",
    "        \n",
    "        return ''.join(reversed(order)) if all(dfs(u) for u in g if u not in states) else\"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        \"\"\"\n",
    "\n",
    "        :param words:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        def get_seq(wordlist):\n",
    "            outm = defaultdict(set)\n",
    "            inm = {}\n",
    "            for k, v in enumerate(wordlist):\n",
    "                for xx in v:\n",
    "                    inm[xx] = 0\n",
    "\n",
    "            for k, v in enumerate(wordlist):\n",
    "                if k == 0:\n",
    "                    continue\n",
    "                pre, item = words[k - 1], words[k]\n",
    "                if item == pre:\n",
    "                    continue\n",
    "                if pre.startswith(item):\n",
    "                    return \"\"\n",
    "\n",
    "                for j in range(min(len(pre), len(item))):\n",
    "                    if pre[j] == item[j]:\n",
    "                        continue\n",
    "                    #outm[pre[j]].add(item[j])\n",
    "                    outm[item[j]].add(pre[j])\n",
    "                    inm[item[j]] += 1\n",
    "                    break\n",
    "            todo = []\n",
    "            for i in inm:\n",
    "                if inm[i] == 0:\n",
    "                    todo.append(i)\n",
    "            if len(todo) == 0:\n",
    "                return [\"\"]\n",
    "            seq = []\n",
    "            used = set()\n",
    "\n",
    "            while todo:\n",
    "                cur = todo.pop(0)\n",
    "                if cur in used:\n",
    "                    continue\n",
    "                used.add(cur)\n",
    "                seq.append(cur)\n",
    "                todel = set()\n",
    "                for i in outm:\n",
    "                    if cur in outm[i]:\n",
    "                        outm[i].remove(cur)\n",
    "                        if len(outm[i]) == 0:\n",
    "                            todel.add(i)\n",
    "\n",
    "                for i in todel:\n",
    "                    todo.append(i)\n",
    "            return seq\n",
    "\n",
    "        ret = get_seq(words)\n",
    "        res = \"\".join(ret)\n",
    "        z1 = set()\n",
    "        for i in words:\n",
    "            for j in i:\n",
    "                z1.add(j)\n",
    "        if len(res) < len(z1):\n",
    "            return \"\"\n",
    "        return res\n",
    "\n",
    "a = Solution()\n",
    "print(a.alienOrder(words=[\"a\",\"b\",\"ca\",\"cc\"]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        g = {}\n",
    "        for c in words[0]:\n",
    "            g[c] = []\n",
    "        for s, t in pairwise(words):\n",
    "            for c in t:\n",
    "                g.setdefault(c, [])\n",
    "            for u, v in zip(s, t):\n",
    "                if u != v:\n",
    "                    g[u].append(v)\n",
    "                    break\n",
    "            else:\n",
    "                if len(s) > len(t):\n",
    "                    return \"\"\n",
    "\n",
    "        VISITING, VISITED = 1, 2\n",
    "        states = {}\n",
    "        order = []\n",
    "        def dfs(u: str) -> bool:\n",
    "            states[u] = VISITING\n",
    "            for v in g[u]:\n",
    "                if v not in states:\n",
    "                    if not dfs(v):\n",
    "                        return False\n",
    "                elif states[v] == VISITING:\n",
    "                    return False\n",
    "            order.append(u)\n",
    "            states[u] = VISITED\n",
    "            return True\n",
    "\n",
    "        return ''.join(reversed(order)) if all(dfs(u) for u in g if u not in states) else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        # set_words = set(words)\n",
    "        # if len(set_words) ==1 :\n",
    "        #     ans = set()\n",
    "        #     for i in set_words:\n",
    "        #         for ii in i:\n",
    "        #             ans.add(ii)\n",
    "        #     return ''.join(ans)\n",
    "\n",
    "        def init_relations():\n",
    "            n = len(words)\n",
    "            relations = collections.defaultdict(set) #这个题可以用set\n",
    "\n",
    "            for i in range(n-1):\n",
    "                word0,word1 = words[i],words[i+1]\n",
    "                n0, n1 = len(word0), len(word1)\n",
    "\n",
    "                if n0 > n1 and word0[:n1] == word1: #当出现异常 判断为错误的 情况时候 返回None \n",
    "                    return None\n",
    "                #!!! 取共同长度 作为搜索空间\n",
    "                search = min(n0,n1)\n",
    "\n",
    "                for k in range(search):\n",
    "                    if word0[k] == word1[k]:\n",
    "                        continue\n",
    "                    # elif word0[k] != word1[k]:\n",
    "                    relations[word0[k]].add(word1[k])\n",
    "                    break\n",
    "            return relations  #当程序正常运行结束但是并没有前后的映射关系时，即所有节点的入度都为0时的特殊情况返回值为空字典而不是none，因此就不用再程序一开始的时候处理特殊情况了\n",
    "            #python 注意函数最终返回值的层数，容易写在末尾的嵌套层数中 导致 输出结果发生变化\n",
    "        realtions = init_relations()\n",
    "        if  realtions is None :  #这里判断是 None 还是 空字典 因此不能写 not realations\n",
    "            return ''\n",
    "        #print(realtions)\n",
    "        # print(g == realtions)\n",
    "        indegree = collections.defaultdict(int)\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            for ii in word:\n",
    "                indegree[ii]\n",
    "\n",
    "        for k,v in realtions.items():\n",
    "            #indegree[k] #在默认字典中 如果 不存在key = k 的键值对，那么直接在字典中添加，后序调用会返回其值\n",
    "            for i in v:\n",
    "                indegree[i] +=1\n",
    "        #print(indegree)\n",
    "        #创建队列\n",
    "        que = collections.deque()\n",
    "        for x,y in indegree.items():\n",
    "            if y == 0:\n",
    "                que.append(x)\n",
    "        cnt = 0\n",
    "        while que:\n",
    "            curr = que.popleft()\n",
    "            ans.append(curr)\n",
    "            cnt +=1 \n",
    "\n",
    "            for s in realtions.keys():\n",
    "                if s == curr:\n",
    "                    for item in realtions[curr]:\n",
    "                        indegree[item] -=1\n",
    "                        if indegree[item] == 0 :\n",
    "                            que.append(item)\n",
    "        return ''.join(ans)  if cnt == len(indegree) else ''\n",
    "        #relation 也可能是空值 比如 \"wrt,wrtkj\"\n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "\n",
    "        indegree = [0] * 26\n",
    "        vol = set()\n",
    "        for w in words:\n",
    "            for ch in w:\n",
    "                vol.add(ch)\n",
    "\n",
    "        tsort = collections.defaultdict(list)\n",
    "        n = len(words)\n",
    "        for i in range(0, n-1):\n",
    "            word_1 = words[i]\n",
    "            word_2 = words[i+1]\n",
    "            min_len = min(len(word_1), len(word_2))\n",
    "            for i in range(min_len):\n",
    "                if word_1[i] != word_2[i]:\n",
    "                    if ord(word_2[i]) - ord(\"a\") not in tsort[ord(word_1[i]) - ord(\"a\")]:\n",
    "                        indegree[ord(word_2[i]) - ord('a')] += 1\n",
    "                        tsort[ord(word_1[i]) - ord(\"a\")].append(ord(word_2[i]) - ord(\"a\") )\n",
    "                    break\n",
    "\n",
    "            else:\n",
    "                if len(word_2) < len(word_1):\n",
    "                    return \"\"\n",
    "\n",
    "        q = list()\n",
    "        res = \"\"\n",
    "\n",
    "        for i in range(len(indegree)):\n",
    "            if indegree[i] == 0:\n",
    "                q.append(i)\n",
    "                # res += chr(i + ord(\"a\"))\n",
    "\n",
    "        while q:\n",
    "            node = q.pop(0)\n",
    "            if node in tsort:\n",
    "                for i in tsort[node]:\n",
    "                    indegree[i] -= 1\n",
    "                    if indegree[i] == 0:\n",
    "                        q.append(i)\n",
    "            if chr(node + ord(\"a\")) in vol:\n",
    "                res += chr(node + ord(\"a\"))\n",
    "\n",
    "        if any(i > 0 for i in indegree):\n",
    "            return \"\"\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "\n",
    "        indegree =  defaultdict(int)\n",
    "        releation = defaultdict(set)\n",
    "        total_node = set()\n",
    "        for i in words:\n",
    "            total_node.update(set(i))\n",
    "        for i in range(1, len(words)):\n",
    "            for j, k in zip(words[i -1], words[i]):\n",
    "                if j != k:\n",
    "                    if k not in releation[j]:\n",
    "                        indegree[k] += 1\n",
    "                        releation[j].add(k)\n",
    "                    break\n",
    "            else:\n",
    "                if len(words[i - 1]) > len(words[i]) and words[i] in words[i - 1]:\n",
    "                    return \"\"\n",
    "        zero = [x for x in total_node if x not in indegree]\n",
    "        res = \"\"\n",
    "        while zero:\n",
    "            t =  zero.pop()\n",
    "            res += t\n",
    "            for i in releation.get(t, []):\n",
    "                indegree[i] -= 1\n",
    "                if indegree[i] == 0:\n",
    "                    zero.append(i)\n",
    "        if len(res) == len(total_node):\n",
    "            return res\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        nodeIndegrees = {}\n",
    "        nodeNeighbors = {}\n",
    "        allLetters = set(words[0])\n",
    "\n",
    "        def addEdge(word1, word2, nodeNeighbors, nodeIndegrees):\n",
    "            idx1 = 0\n",
    "            idx2 = 0\n",
    "            while idx1 < len(word1) and idx2 < len(word2):\n",
    "                if word1[idx1] == word2[idx2]:\n",
    "                    idx1 += 1\n",
    "                    idx2 += 1\n",
    "                else:\n",
    "                    # add new\n",
    "                    if word1[idx1] not in nodeNeighbors:\n",
    "                        nodeNeighbors[word1[idx1]] = set()\n",
    "                    # existing edge\n",
    "                    if word2[idx2] in nodeNeighbors[word1[idx1]]:\n",
    "                        return True\n",
    "                    nodeNeighbors[word1[idx1]].add(word2[idx2])\n",
    "                    # update in-degree\n",
    "                    if word2[idx2] not in nodeIndegrees:\n",
    "                        nodeIndegrees[word2[idx2]] = 0\n",
    "                    nodeIndegrees[word2[idx2]] += 1\n",
    "                    return True\n",
    "            return len(word1) <= len(word2)\n",
    "        \n",
    "        for idx in range(1, len(words)):\n",
    "            if not addEdge(words[idx - 1], words[idx], nodeNeighbors, nodeIndegrees):\n",
    "                return ''\n",
    "            for letter in words[idx]:\n",
    "                allLetters.add(letter)\n",
    "        \n",
    "        queue = []\n",
    "        for letter in allLetters:\n",
    "            if letter in nodeIndegrees:\n",
    "                continue\n",
    "            queue.append(letter)\n",
    "        \n",
    "        sortedLetters = []\n",
    "        while queue:\n",
    "            curLetter = queue.pop()\n",
    "            sortedLetters.append(curLetter)\n",
    "            if curLetter not in nodeNeighbors:\n",
    "                continue\n",
    "            for neighbor in nodeNeighbors[curLetter]:\n",
    "                nodeIndegrees[neighbor] -= 1\n",
    "                if nodeIndegrees[neighbor] == 0:\n",
    "                    queue.append(neighbor)\n",
    "        \n",
    "        # invalid, existing cycle in graph\n",
    "        if len(sortedLetters) != len(allLetters):\n",
    "            return ''\n",
    "        return ''.join(sortedLetters)\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "'''\n",
    "topology sort\n",
    "the smallest letter having in-degree 0\n",
    "\n",
    "1. build directed graph,\n",
    "    compre word[i] and word[i + 1], get directed edge\n",
    "2. topology sort\n",
    "start from 0 in-degree nodes, then remove and update degrees\n",
    "\n",
    "nodes = {} k is letter, val is it's neighbors\n",
    "indegrees {}, k is letter, val is indegree\n",
    "\n",
    "\n",
    "\n",
    "queue = [node having indegree 0]\n",
    "letters = []\n",
    "while queue:\n",
    "    curNode = queue.pop()\n",
    "    letters.append(curNode)\n",
    "    for child in nodes[curNode]:\n",
    "        indegrees[child] -= 1\n",
    "        if indegrees[child] == 0:\n",
    "            queue.append(child)\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        adj_list = collections.defaultdict(list)\n",
    "        in_degree = collections.Counter({ch : 0 for word in words for ch in word})\n",
    "\n",
    "        for first_word, second_word in zip(words, words[1:]):\n",
    "            for ch1, ch2 in zip(first_word, second_word):\n",
    "                if ch1 != ch2:\n",
    "                    if ch2 not in adj_list[ch1]:\n",
    "                        adj_list[ch1].append(ch2)\n",
    "                        in_degree[ch2] += 1\n",
    "                    break\n",
    "            else:\n",
    "                if len(second_word) < len(first_word):\n",
    "                    return \"\"\n",
    "\n",
    "        output = []\n",
    "        q = collections.deque([ch for ch in in_degree if in_degree[ch] == 0])\n",
    "        while q:\n",
    "            prev = q.popleft()\n",
    "            output.append(prev)\n",
    "            for curr in adj_list[prev]:\n",
    "                in_degree[curr] -= 1\n",
    "                if in_degree[curr] == 0:\n",
    "                    q.append(curr)\n",
    "        \n",
    "        if len(output) < len(in_degree):\n",
    "            return \"\"\n",
    "        return \"\".join(output)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for i in range(1, len(words)):\n",
    "            w1, w2 = words[i-1], words[i]\n",
    "            j = 0\n",
    "            while j<len(w1) and j<len(w2):\n",
    "                if w1[j]!=w2[j]:\n",
    "                    graph[w1[j]].append(w2[j])\n",
    "                    break\n",
    "                j+=1\n",
    "            if j==len(w2) and len(w2)<len(w1):\n",
    "                return \"\"\n",
    "        \n",
    "        res = []\n",
    "        visited = [0]*26\n",
    "        def dfs(c):\n",
    "            order = ord(c)-ord(\"a\")\n",
    "            if visited[order]==1:\n",
    "                return False\n",
    "\n",
    "            if visited[order]==2:\n",
    "                return True\n",
    "            \n",
    "            visited[order]=1\n",
    "            for nb in graph[c]:\n",
    "                if not dfs(nb):\n",
    "                    return False\n",
    "            visited[order]=2\n",
    "            res.append(c)\n",
    "            return True\n",
    "        \n",
    "        for w in words:\n",
    "            for c in w:\n",
    "                if not dfs(c):\n",
    "                    return \"\"\n",
    "        return \"\".join(res[::-1])\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        indegree = {}\n",
    "\n",
    "        g = defaultdict(list)\n",
    "\n",
    "        s = set()\n",
    "\n",
    "        for w in words:\n",
    "            s = s.union(set(w))\n",
    "\n",
    "        # # populate g and indegree\n",
    "        # # \n",
    "        # for word in words:\n",
    "        #     for ch in word:\n",
    "        #         if ch not in indegree:\n",
    "        #             indegree[ch] = 0\n",
    "\n",
    "\n",
    "        for w1, w2 in pairwise(words):\n",
    "            n1, n2 = len(w1), len(w2)\n",
    "\n",
    "            if n1 > n2:\n",
    "                if w1[:n2] == w2: # invalid word that we cannot find order\n",
    "                    # g = defaultdict(list)\n",
    "                    # continue\n",
    "                    return \"\"\n",
    "                \n",
    "            min_n = min(n1, n2)\n",
    "\n",
    "\n",
    "            for i in range(min_n):\n",
    "                if w1[i] != w2[i]:\n",
    "                    g[w1[i]].append(w2[i]) # as w1 presents before w2\n",
    "                    break\n",
    "\n",
    "                    # else:\n",
    "                    # indegree[w2[i]] += 1\n",
    "\n",
    "        # def init_graph():\n",
    "        #     g, n = defaultdict(set), len(words)\n",
    "        #     for i in range(n - 1):\n",
    "        #         word0, word1 = words[i], words[i + 1]\n",
    "        #         n0, n1 = len(word0), len(word1)\n",
    "        #         # 形如[\"abc\", \"ab\"]的样例是违反定义的, 特殊判断\n",
    "        #         if n0 > n1 and word0[:n1] == word1:\n",
    "        #             return None\n",
    "                \n",
    "        #         m = min(n0, n1)\n",
    "        #         for j in range(m):\n",
    "        #             if word0[j] == word1[j]:\n",
    "        #                 continue\n",
    "        #             # 第一对不同的字符提供序关系, 后面的字符忽略\n",
    "        #             g[word0[j]].add(word1[j])\n",
    "        #             break\n",
    "        #     return g\n",
    "\n",
    "        # g = init_graph()\n",
    "        # if g is None:\n",
    "        #     return \"\"\n",
    "\n",
    "\n",
    "                    # break # only the first different letter matters\n",
    "            \n",
    "        def count_in_degree(g):\n",
    "            degree = {}\n",
    "            # 将出现字符的入度初始化为0\n",
    "            for word in words:\n",
    "                for ch in word:  \n",
    "                    degree[ch] = 0\n",
    "            \n",
    "            for char, charset in g.items():\n",
    "                for ch in charset:\n",
    "                    degree[ch] += 1\n",
    "            return degree\n",
    "\n",
    "        indegree = count_in_degree(g)\n",
    "        # populate q\n",
    "        q = deque()\n",
    "\n",
    "        for key in indegree.keys():\n",
    "            # letter = chr(i + ord('a'))\n",
    "            if indegree[key] == 0:\n",
    "                q.append(key)\n",
    "        res = []\n",
    "\n",
    "        \n",
    "\n",
    "        while q: # only has indegree=0 nodes\n",
    "\n",
    "            ch = q.popleft() # indegree=0 nodes ( no above parent)\n",
    "            res.append(ch)\n",
    "            for child in g[ch]:\n",
    "                indegree[child] -= 1 # as we removed ch, which is the parent for child\n",
    "                if indegree[child] == 0:\n",
    "                    # add to q as q has only nodes with indegree==0\n",
    "                    q.append(child)\n",
    "        \n",
    "        return ''.join(res) if len(res) == len(s) else \"\"# when q is empty, we finished all topo sort, all letters must be presented in the \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        def init_graph():\n",
    "            g, n = defaultdict(set), len(words)\n",
    "            for i in range(n - 1):\n",
    "                word0, word1 = words[i], words[i + 1]\n",
    "                n0, n1 = len(word0), len(word1)\n",
    "                # 形如[\"abc\", \"ab\"]的样例是违反定义的, 特殊判断\n",
    "                if n0 > n1 and word0[:n1] == word1:\n",
    "                    return None\n",
    "                \n",
    "                m = min(n0, n1)\n",
    "                for j in range(m):\n",
    "                    if word0[j] == word1[j]:\n",
    "                        continue\n",
    "                    # 第一对不同的字符提供序关系, 后面的字符忽略\n",
    "                    g[word0[j]].add(word1[j])\n",
    "                    break\n",
    "            return g\n",
    "        \n",
    "        def count_in_degree(g):\n",
    "            degree = {}\n",
    "            # 将出现字符的入度初始化为0\n",
    "            for word in words:\n",
    "                for ch in word:  \n",
    "                    degree[ch] = 0\n",
    "            \n",
    "            for char, charset in g.items():\n",
    "                for ch in charset:\n",
    "                    degree[ch] += 1\n",
    "            return degree\n",
    "        \n",
    "        g = init_graph()\n",
    "        if g is None:\n",
    "            return \"\"\n",
    "        in_degree = count_in_degree(g)\n",
    "        \n",
    "        queue, count = deque(), 0\n",
    "        for char, degree in in_degree.items():\n",
    "            count += 1\n",
    "            if degree == 0:\n",
    "                queue.append(char)\n",
    "            \n",
    "        order = \"\"\n",
    "        while queue:\n",
    "            ch = queue.popleft()\n",
    "            order += ch\n",
    "            \n",
    "            if ch in g:\n",
    "                for c in g[ch]:\n",
    "                    in_degree[c] -= 1\n",
    "                    if in_degree[c] == 0:\n",
    "                        queue.append(c)\n",
    "        print(order, count)\n",
    "        return order if len(order) == count else \"\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        n = len(words)\n",
    "        edges = {}\n",
    "        appearence = [False for _ in range(26)]\n",
    "        degree = [0 for _ in range(26)]\n",
    "        a_num = ord('a')\n",
    "        for x in words[0]:\n",
    "            appearence[ord(x)-a_num] = True\n",
    "        flag = True\n",
    "        s1 = \"\"\n",
    "        s2 = \"\"\n",
    "        for i in range(1,n):\n",
    "            s1 = words[i-1]\n",
    "            s2 = words[i]\n",
    "            for x in s2:\n",
    "                appearence[ord(x)-a_num] = True\n",
    "            m = min(len(s1),len(s2))\n",
    "            flag = True\n",
    "            for j in range(m):\n",
    "                if s1[j] == s2[j]:\n",
    "                    continue\n",
    "                x = ord(s1[j])-a_num\n",
    "                y = ord(s2[j])-a_num\n",
    "                edges.setdefault(x,set())\n",
    "                if y not in edges[x]:\n",
    "                    edges[x].add(y)\n",
    "                    degree[y] += 1\n",
    "                    flag = False\n",
    "                break\n",
    "            if flag and j == m - 1 and m != len(s1):\n",
    "                return \"\"\n",
    "        ans = \"\"\n",
    "        q = []\n",
    "        for i in range(25,-1,-1):\n",
    "            if appearence[i] and not degree[i]:\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            now = q.pop()\n",
    "            appearence[now] = False\n",
    "            ans += chr(now+a_num)\n",
    "            if now not in edges:\n",
    "                continue\n",
    "            for y in edges[now]:\n",
    "                degree[y] -= 1\n",
    "                if not degree[y]:\n",
    "                    q.append(y)\n",
    "        for i in range(26):\n",
    "            if degree[i]:\n",
    "                return \"\"\n",
    "            if appearence[i]:\n",
    "                ans += chr(i + a_num)\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        deg = [-1]*26\n",
    "        g = defaultdict(list)\n",
    "        n = len(words)\n",
    "        occur = set()\n",
    "        if len(words) == 1:\n",
    "            return \"\".join(set(words[0]))\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                for c in words[i] + words[j]:\n",
    "                    occur.add(c)\n",
    "                if words[i] == words[j]:\n",
    "                    if j>i+1:\n",
    "                        return \"\"\n",
    "                    continue\n",
    "                if words[j] == words[i][:len(words[j])]:\n",
    "                    return \"\"\n",
    "                k = 0\n",
    "                while k<len(words[i]) and k<len(words[j]) and words[i][k] == words[j][k]:\n",
    "                    k+=1\n",
    "                if k>=len(words[i]) or k>=len(words[j]):\n",
    "                    continue\n",
    "                ik = ord(words[i][k]) - 97\n",
    "                jk = ord(words[j][k]) - 97\n",
    "                if jk not in g[ik]:\n",
    "                    if deg[jk] == -1:\n",
    "                        deg[jk] = 0\n",
    "                    deg[jk] +=1\n",
    "                    g[ik].append(jk)\n",
    "        # print(deg)\n",
    "        for o in occur:\n",
    "            if deg[ord(o)-97] == -1:\n",
    "                deg[ord(o)-97] = 0\n",
    "        q = []\n",
    "        for i,d in enumerate(deg):\n",
    "            # if d>=0:\n",
    "            #     print(chr(i+97))\n",
    "            if d == 0:\n",
    "                q.append(i)\n",
    "        ans = \"\"\n",
    "\n",
    "        # print(g)\n",
    "        # print(deg)\n",
    "        while q:\n",
    "            # print([chr(v+97) for v in q],q)\n",
    "            nxt_q = []\n",
    "            for c in q:\n",
    "                ans += chr(c+97)\n",
    "                for nxt in g[c]:\n",
    "                    deg[nxt]-=1\n",
    "                    if deg[nxt] == 0:\n",
    "                        nxt_q.append(nxt)\n",
    "            q = nxt_q\n",
    "        if any(d>0 for d in deg):\n",
    "            return \"\"\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "         # bulid the graph\n",
    "        graph= {c:set() for word in words for c in word}\n",
    "        n,count = len(words),len(graph)\n",
    "\n",
    "        for i in range(n-1):\n",
    "            minLen = min(len(words[i]),len(words[i+1]))\n",
    "            if len(words[i]) > len(words[i+1]) and words[i][:minLen] == words[i+1][:minLen]:\n",
    "                return \"\"\n",
    "            \n",
    "            for j in range(minLen):\n",
    "                if words[i][j] != words[i+1][j]:\n",
    "                    graph[words[i][j]].add(words[i+1][j])\n",
    "                    break\n",
    "        \n",
    "        if graph is None:\n",
    "            return \"\"\n",
    "        \n",
    "        # get the degree, the ch with degree 0 is the root \n",
    "        \n",
    "        degree = {n:0 for n in graph}\n",
    "        for _,chset in graph.items():\n",
    "            for ch in chset:\n",
    "                degree[ch] += 1\n",
    "        \n",
    "        queue = deque()\n",
    "        for char, deg in degree.items():\n",
    "            if deg ==0:\n",
    "                queue.append(char)\n",
    "        \n",
    "        order = \"\"\n",
    "        \n",
    "        # every time append the \"ch\" with zero degree and minus the degree of its children\n",
    "        while queue:\n",
    "            ch = queue.popleft()\n",
    "            order += ch\n",
    "\n",
    "            \n",
    "            for children in graph[ch]:\n",
    "                degree[children] -=1\n",
    "                if degree[children] ==0:\n",
    "                    queue.append(children)\n",
    "        \n",
    "        return order if len(order) == count else \"\"\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "    \n",
    "       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        def diff(s1,s2):\n",
    "            n1,n2 = len(s1),len(s2)\n",
    "            i,j = 0,0\n",
    "            flag = False\n",
    "            while i<n1 and j<n2:\n",
    "                if not flag and s1[i]!=s2[j]:\n",
    "                    edges[ord(s1[i])-ord('a')].append(ord(s2[j])-ord('a'))\n",
    "                    deg[ord(s2[j])-ord('a')]+=1\n",
    "                    flag = True\n",
    "                else:\n",
    "                    if ord(s1[i])-ord('a') not in edges:\n",
    "                        edges[ord(s1[i])-ord('a')]=[]\n",
    "                    if ord(s2[j])-ord('a') not in edges:\n",
    "                        edges[ord(s2[j])-ord('a')]=[]\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "            if i==n1:\n",
    "                while j<n2:\n",
    "                    if ord(s2[j])-ord('a') not in edges:\n",
    "                        edges[ord(s2[j])-ord('a')]=[]\n",
    "                    j+=1\n",
    "            elif j==n2:\n",
    "                while i<n1:\n",
    "                    if ord(s1[i])-ord('a') not in edges:\n",
    "                        edges[ord(s1[i])-ord('a')]=[]\n",
    "                    i+=1\n",
    "            return\n",
    "\n",
    "\n",
    "        edges = collections.defaultdict(list)\n",
    "        deg = [0]*26\n",
    "        res = []\n",
    "\n",
    "        n = len(words)\n",
    "        if n==1:\n",
    "            return ''.join(list(set(words[0])))\n",
    "        for i in range(n-1):\n",
    "            if len(words[i+1])<len(words[i]) and words[i+1]==words[i][0:len(words[i+1])]:\n",
    "                return \"\"\n",
    "            diff(words[i],words[i+1])\n",
    "        q = collections.deque([u for u in range(26) if u in edges and deg[u]==0])\n",
    "        while q:\n",
    "            u = q.popleft()\n",
    "            res.append(chr(u+ord('a')))\n",
    "            for v in edges[u]:\n",
    "                deg[v]-=1\n",
    "                if deg[v]==0:\n",
    "                    q.append(v)\n",
    "        return ''.join(res) if len(res)==len(edges) else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        # Construct the graph\n",
    "        graph = defaultdict(set)\n",
    "        indegree = {c: 0 for word in words for c in word}\n",
    "        for pair in zip(words, words[1:]):\n",
    "            if len(pair[0]) > len(pair[1]) and pair[0][:len(pair[1])] == pair[1]:\n",
    "                    return ''\n",
    "            for a, b in zip(*pair):\n",
    "                if a != b:\n",
    "                    if b not in graph[a]:\n",
    "                        indegree[b] += 1\n",
    "                    graph[a].add(b)\n",
    "                    break\n",
    "        # Perform a topological sort\n",
    "        queue = deque([c for c in indegree if indegree[c] == 0])\n",
    "        order = []\n",
    "        while queue:\n",
    "            c = queue.popleft()\n",
    "            order.append(c)\n",
    "            for neighbor in graph[c]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if indegree[neighbor] == 0:\n",
    "                    queue.append(neighbor)\n",
    "        # Check if there is a cycle\n",
    "        if len(order) < len(indegree):\n",
    "            return \"\"\n",
    "        return \"\".join(order)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        #解题思路：\n",
    "        #小->大,记录每个字母之后的字母顺序，即出度；并记录每个字母的入度，建图\n",
    "        #进行拓扑排序即可\n",
    "\n",
    "        indeg= {}\n",
    "        for word in words:\n",
    "            for w in word:\n",
    "                indeg[w] = 0\n",
    "        \n",
    "        n = len(words)\n",
    "        graph = collections.defaultdict(list)\n",
    "        for i in range(n - 1):\n",
    "            word0 = words[i]\n",
    "            word1 = words[i + 1]\n",
    "            if len(word0) > len(word1) and word0[:len(word1)] == word1:\n",
    "                return ''\n",
    "            for k in range(min(len(word0),len(word1))):\n",
    "                if word0[k] == word1[k]:\n",
    "                    continue\n",
    "                elif word1[k] not in graph[word0[k]]:\n",
    "                    graph[word0[k]].append(word1[k])\n",
    "                    indeg[word1[k]] += 1\n",
    "                    break\n",
    "                else:\n",
    "                    break\n",
    "        \n",
    "        res = ''\n",
    "        q = [i for i in indeg if indeg[i] == 0]\n",
    "        i = 0\n",
    "        while i < len(q):\n",
    "            res += q[i]\n",
    "            for s in graph[q[i]]:\n",
    "                indeg[s] -= 1\n",
    "                if indeg[s] == 0:\n",
    "                    q.append(s)\n",
    "            i += 1\n",
    "        return res if i == len(indeg) else ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        graph = self.create_graph(words)\n",
    "        if not graph:\n",
    "            return \"\"\n",
    "        print(graph)\n",
    "        indegree = {i:0 for i in graph}\n",
    "        for k, v in graph.items():\n",
    "            for j in v:\n",
    "                indegree[j] += 1\n",
    "        print(indegree)\n",
    "        queue = collections.deque()\n",
    "        for k, v in indegree.items():\n",
    "            if v == 0:\n",
    "                queue.append(k)\n",
    "        \n",
    "        order = []\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            order.append(node)\n",
    "            for next_node in graph[node]:\n",
    "                indegree[next_node] -= 1\n",
    "                if indegree[next_node] == 0:\n",
    "                    queue.append(next_node)\n",
    "        if len(order) == len(graph):\n",
    "            return \"\".join(order)\n",
    "        return \"\"\n",
    "\n",
    "    def get_all_characters(self, words):\n",
    "        hashset = set()\n",
    "        for word in words:\n",
    "            for c in word:\n",
    "                hashset.add(c)\n",
    "        return hashset      \n",
    "\n",
    "    def create_graph(self, words):\n",
    "        all_characters = self.get_all_characters(words)\n",
    "        graph = {i:set() for i in all_characters}\n",
    "        for i in range(len(words) - 1):\n",
    "            word1 = words[i]\n",
    "            word2 = words[i + 1]\n",
    "            if not self.get_order(word1, word2, graph):\n",
    "                return None\n",
    "        return graph\n",
    "\n",
    "    def get_order(self, word1, word2, graph):\n",
    "        for i in range(min(len(word1), len(word2))):\n",
    "            if word1[i] != word2[i]:\n",
    "                graph[word1[i]].add(word2[i])\n",
    "                return True\n",
    "        if i < len(word1) - 1 and i == len(word2) - 1:    \n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        g = {}\n",
    "        for c in words[0]:\n",
    "            g[c] = []\n",
    "        for s, t in pairwise(words):\n",
    "            for c in t:\n",
    "                g.setdefault(c, [])\n",
    "            for u, v in zip(s, t):\n",
    "                if u != v:\n",
    "                    g[u].append(v)\n",
    "                    break\n",
    "            else:\n",
    "                if len(s) > len(t):\n",
    "                    return \"\"\n",
    "\n",
    "        VISITING, VISITED = 1, 2\n",
    "        states = {}\n",
    "        order = []\n",
    "        def dfs(u: str) -> bool:\n",
    "            states[u] = VISITING\n",
    "            for v in g[u]:\n",
    "                if v not in states:\n",
    "                    if not dfs(v):\n",
    "                        return False\n",
    "                elif states[v] == VISITING:\n",
    "                    return False\n",
    "            order.append(u)\n",
    "            states[u] = VISITED\n",
    "            return True\n",
    "\n",
    "        return ''.join(reversed(order)) if all(dfs(u) for u in g if u not in states) else \"\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        edges = collections.defaultdict(list)\n",
    "        indegree = collections.defaultdict(int)\n",
    "        for i in range(len(words)):\n",
    "            for j in range(len(words[i])):\n",
    "                if words[i][j] not in indegree:\n",
    "                    indegree[words[i][j]] = 0\n",
    "        for i in range(1, len(words)):\n",
    "            for j in range(min(len(words[i-1]), len(words[i]))):\n",
    "                if words[i-1][j] != words[i][j]:\n",
    "                    if words[i][j] not in edges[words[i-1][j]]:\n",
    "                        edges[words[i-1][j]].append(words[i][j])\n",
    "                        indegree[words[i][j]] += 1\n",
    "                    break\n",
    "                if j == min(len(words[i-1]), len(words[i])) - 1 and len(words[i-1]) > len(words[i]):\n",
    "                    return \"\"\n",
    "\n",
    "        q = [s for s in indegree.keys() if indegree[s] == 0]\n",
    "        res = \"\"\n",
    "        while q:\n",
    "            u = q.pop(0)\n",
    "            res += u\n",
    "            for v in edges[u]:\n",
    "                indegree[v] -= 1\n",
    "                if indegree[v] == 0:\n",
    "                    q.append(v)\n",
    "        return res if len(res) == len(edges) else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        def init_graph():\n",
    "            g, n = defaultdict(set), len(words)\n",
    "            for i in range(n - 1):\n",
    "                word0, word1 = words[i], words[i + 1]\n",
    "                n0, n1 = len(word0), len(word1)\n",
    "                # 形如[\"abc\", \"ab\"]的样例是违反定义的, 特殊判断\n",
    "                if n0 > n1 and word0[:n1] == word1:\n",
    "                    return None\n",
    "                \n",
    "                m = min(n0, n1)\n",
    "                for j in range(m):\n",
    "                    if word0[j] == word1[j]:\n",
    "                        continue\n",
    "                    # 第一对不同的字符提供序关系, 后面的字符忽略\n",
    "                    g[word0[j]].add(word1[j])\n",
    "                    break\n",
    "            return g\n",
    "        \n",
    "        def count_in_degree(g):\n",
    "            degree = {}\n",
    "            # 将出现字符的入度初始化为0\n",
    "            for word in words:\n",
    "                for ch in word:  \n",
    "                    degree[ch] = 0\n",
    "            \n",
    "            for char, charset in g.items():\n",
    "                for ch in charset:\n",
    "                    degree[ch] += 1\n",
    "            return degree\n",
    "        \n",
    "        g = init_graph()\n",
    "        if g is None:\n",
    "            return \"\"\n",
    "        in_degree = count_in_degree(g)\n",
    "        \n",
    "        queue, count = deque(), 0\n",
    "        for char, degree in in_degree.items():\n",
    "            count += 1\n",
    "            if degree == 0:\n",
    "                queue.append(char)\n",
    "            \n",
    "        order = \"\"\n",
    "        while queue:\n",
    "            ch = queue.popleft()\n",
    "            order += ch\n",
    "            \n",
    "            if ch in g:\n",
    "                for c in g[ch]:\n",
    "                    in_degree[c] -= 1\n",
    "                    if in_degree[c] == 0:\n",
    "                        queue.append(c)\n",
    "        return order if len(order) == count else \"\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        # set_words = set(words)\n",
    "        # if len(set_words) ==1 :\n",
    "        #     ans = set()\n",
    "        #     for i in set_words:\n",
    "        #         for ii in i:\n",
    "        #             ans.add(ii)\n",
    "        #     return ''.join(ans)\n",
    "\n",
    "        def init_relations():\n",
    "            n = len(words)\n",
    "            relations = collections.defaultdict(set) #这个题可以用set\n",
    "\n",
    "            for i in range(n-1):\n",
    "                word0,word1 = words[i],words[i+1]\n",
    "                n0, n1 = len(word0), len(word1)\n",
    "\n",
    "                if n0 > n1 and word0[:n1] == word1: #当出现异常 判断为错误的 情况时候 返回None \n",
    "                    return None\n",
    "                #!!! 取共同长度 作为搜索空间\n",
    "                search = min(n0,n1)\n",
    "\n",
    "                for k in range(search):\n",
    "                    if word0[k] == word1[k]:\n",
    "                        continue\n",
    "                    # elif word0[k] != word1[k]:\n",
    "                    relations[word0[k]].add(word1[k])\n",
    "                    break\n",
    "            return relations  #当程序正常运行结束但是并没有前后的映射关系时，即所有节点的入度都为0时的特殊情况返回值为空字典而不是none，因此就不用再程序一开始的时候处理特殊情况了\n",
    "            #python 注意函数最终返回值的层数，容易写在末尾的嵌套层数中 导致 输出结果发生变化\n",
    "        realtions = init_relations()\n",
    "        if  realtions is None :  #这里判断是 None 还是 空字典 因此不能写 not realations\n",
    "            return ''\n",
    "        print(realtions)\n",
    "        # print(g == realtions)\n",
    "        indegree = collections.defaultdict(int)\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            for ii in word:\n",
    "                indegree[ii]\n",
    "\n",
    "        for k,v in realtions.items():\n",
    "            #indegree[k] #在默认字典中 如果 不存在key = k 的键值对，那么直接在字典中添加，后序调用会返回其值\n",
    "            for i in v:\n",
    "                indegree[i] +=1\n",
    "        print(indegree)\n",
    "        #创建队列\n",
    "        que = collections.deque()\n",
    "        for x,y in indegree.items():\n",
    "            if y == 0:\n",
    "                que.append(x)\n",
    "        cnt = 0\n",
    "        while que:\n",
    "            curr = que.popleft()\n",
    "            ans.append(curr)\n",
    "            cnt +=1 \n",
    "\n",
    "            for s in realtions.keys():\n",
    "                if s == curr:\n",
    "                    for item in realtions[curr]:\n",
    "                        indegree[item] -=1\n",
    "                        if indegree[item] == 0 :\n",
    "                            que.append(item)\n",
    "        return ''.join(ans)  if cnt == len(indegree) else ''\n",
    "        #relation 也可能是空值 比如 \"wrt,wrtkj\"\n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        self.unvisited = set()\n",
    "        self.visiting = set()\n",
    "        self.e = defaultdict(set)\n",
    "        for w in words:\n",
    "            for c in w:\n",
    "                self.unvisited.add(c)\n",
    "        for w1, w2 in zip(words[:-1], words[1:]):\n",
    "            i1, i2 = 0, 0\n",
    "            while i1 < len(w1) and i2 < len(w2):\n",
    "                if w1[i1] != w2[i2]:\n",
    "                    self.e[w1[i1]].add(w2[i2])\n",
    "                    break\n",
    "                i1 += 1\n",
    "                i2 += 1\n",
    "            else:\n",
    "                if i1 < len(w1):\n",
    "                    return ''\n",
    "        self.ans = ''\n",
    "        while len(self.unvisited):\n",
    "            v = self.unvisited.pop()\n",
    "            if not self.visit(v):\n",
    "                return ''\n",
    "        return self.ans\n",
    "        \n",
    "    def visit(self, c):\n",
    "        self.visiting.add(c)\n",
    "        for v in self.e[c]:\n",
    "            if v in self.visiting:\n",
    "                return False\n",
    "            if v in self.unvisited:\n",
    "                self.unvisited.remove(v)\n",
    "                if not self.visit(v):\n",
    "                    return False\n",
    "        self.visiting.remove(c)\n",
    "        self.ans = c + self.ans\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        n = len(words)\n",
    "        g = defaultdict(list)\n",
    "        indeg = defaultdict(int) \n",
    "        def add_edge(s1, s2):\n",
    "            l1,l2 = len(s1),len(s2)\n",
    "            i = 0 \n",
    "            while i < min(l1,l2):\n",
    "                if s1[i] == s2[i]:\n",
    "                    i+=1\n",
    "                else:\n",
    "                    g[s1[i]].append(s2[i])\n",
    "                    return True \n",
    "            if l1 > l2:\n",
    "                return False \n",
    "            return True \n",
    "\n",
    "        letters = set() \n",
    "        for i in range(n):\n",
    "            for c in words[i]:\n",
    "                letters.add(c) \n",
    "            for j in range(i+1, n):\n",
    "                if not add_edge(words[i], words[j]):\n",
    "                    return ''\n",
    "        #print(g) \n",
    "        for a, adj in g.items():\n",
    "            for x in adj:\n",
    "                indeg[x] += 1\n",
    "        Q = deque() \n",
    "        for c in letters:\n",
    "            if indeg[c] == 0:\n",
    "                Q.append(c) \n",
    "        #print(Q) \n",
    "        ans = []\n",
    "        while Q:\n",
    "            #print(Q) \n",
    "            u = Q.popleft() \n",
    "            ans.append(u) \n",
    "            for v in g[u]:\n",
    "                indeg[v] -= 1\n",
    "                if indeg[v] == 0:\n",
    "                    Q.append(v) \n",
    "        if len(ans) == len(letters):\n",
    "            return ''.join(ans)  \n",
    "        return '' \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        graph = defaultdict(list)\n",
    "        for word in words:\n",
    "            for w in word:\n",
    "                if w not in graph:\n",
    "                    graph[w] = []\n",
    "        \n",
    "        for i in range(len(words) - 1):\n",
    "            j = 0\n",
    "            while j < len(words[i]) and j < len(words[i+1]):\n",
    "                if words[i][j] != words[i+1][j]:\n",
    "                    graph[words[i][j]].append(words[i+1][j])\n",
    "                    break\n",
    "                j += 1\n",
    "        \n",
    "        in_degrees = {}\n",
    "        order = []\n",
    "        for k in graph:\n",
    "            in_degrees[k] = 0\n",
    "        \n",
    "        for values in graph.values():\n",
    "            for value in values:\n",
    "                in_degrees[value] += 1\n",
    "            \n",
    "        zeros = [k for k, v in in_degrees.items() if v == 0]\n",
    "        q = []\n",
    "        while zeros:\n",
    "            node = zeros.pop()\n",
    "            q.append(node)\n",
    "            order.append(node)\n",
    "            for value in graph[node]:\n",
    "                in_degrees[value] -= 1\n",
    "                if in_degrees[value] == 0:\n",
    "                    zeros.append(value)\n",
    "        \n",
    "        is_unval = False\n",
    "        if len(order) != len(graph):\n",
    "            is_unval = True\n",
    "        for i in range(len(words)-1):\n",
    "            if len(words[i]) > len(words[i+1]) and words[i][:len(words[i+1])] == words[i+1]:\n",
    "                is_unval = True\n",
    "                break\n",
    "        \n",
    "        if is_unval: return \"\"\n",
    "        if not order:\n",
    "            return \"\".join([k for k in graph])\n",
    "        return \"\".join(order)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        parent_dict, degree, exist_word = {}, [0]*26, set()\n",
    "        for i in range(len(words)-1):\n",
    "            word1, word2 = words[i], words[i+1]\n",
    "            for j in range(min(len(word1), len(word2))):\n",
    "                if word1[j] != word2[j]:\n",
    "                    if word1[j] not in parent_dict:\n",
    "                        parent_dict[word1[j]] = [word2[j]]\n",
    "                        degree[ord(word2[j])-ord('a')] += 1\n",
    "                    else:\n",
    "                        if word2[j] not in parent_dict[word1[j]]:\n",
    "                            parent_dict[word1[j]].append(word2[j])\n",
    "                            degree[ord(word2[j])-ord('a')] += 1\n",
    "                    break\n",
    "            if len(word1) > len(word2) and word1[:len(word2)] == word2:\n",
    "                return ''\n",
    "        for word in words:\n",
    "            for letter in word:\n",
    "                exist_word.add(letter)\n",
    "        \n",
    "        intial_lis = []\n",
    "        for i in range(26):\n",
    "            if degree[i] == 0 and chr(ord('a')+i) in exist_word:\n",
    "                intial_lis += [chr(ord('a')+i)]\n",
    "        res = ''\n",
    "        while intial_lis:\n",
    "            res += ''.join(intial_lis)\n",
    "            new_lis = []\n",
    "            for elm in intial_lis:\n",
    "                if elm in parent_dict:\n",
    "                    for nxt in parent_dict[elm]:\n",
    "                        degree[ord(nxt) - ord('a')] -= 1\n",
    "                        if degree[ord(nxt) - ord('a')] == 0:\n",
    "                            new_lis.append(nxt)\n",
    "            intial_lis = new_lis\n",
    "        \n",
    "        return res if sum(degree) == 0 else ''\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        def init_graph():\n",
    "            graph=collections.defaultdict(set)\n",
    "            n=len(words)\n",
    "            for i in range(n-1):\n",
    "                word0,word1=words[i],words[i+1]\n",
    "                m1=len(word0)\n",
    "                m2=len(word1)\n",
    "                if m1>m2 and word0[:m2]==word1[:m2]:\n",
    "                    return None\n",
    "                min_length=min(m1,m2)\n",
    "                for i in range(min_length):\n",
    "                    if word0[i]==word1[i]:\n",
    "                        continue\n",
    "                    graph[word0[i]].add(word1[i])\n",
    "                    break\n",
    "            return graph\n",
    "        g=init_graph()\n",
    "        if g is None:\n",
    "            return \"\"\n",
    "        def in_degree(g):\n",
    "            degree={}\n",
    "            for word in words:\n",
    "                for ch in word:\n",
    "                    degree[ch]=0\n",
    "            for key,values in g.items():\n",
    "                for char in values:\n",
    "                    degree[char]+=1\n",
    "            return degree\n",
    "\n",
    "        degree=in_degree(g)\n",
    "        cnt=0\n",
    "        q=deque()\n",
    "        for char,value in degree.items():\n",
    "            cnt+=1\n",
    "            if value==0:\n",
    "                q.append(char)\n",
    "        res=\"\"\n",
    "        while q:\n",
    "            node=q.popleft()\n",
    "            res+=node\n",
    "            next_chars=g[node]\n",
    "            for char in next_chars:\n",
    "                degree[char]-=1\n",
    "                if degree[char]==0:\n",
    "                    q.append(char)\n",
    "        return res if len(res)==cnt else \"\"\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "\n",
    "        graph = {}\n",
    "\n",
    "        indegree = {}\n",
    "\n",
    "        for c in words[0]:\n",
    "            indegree[c] = 0\n",
    "        \n",
    "        for i in range(len(words) - 1):\n",
    "            word1 = words[i]\n",
    "            word2 = words[i + 1]\n",
    "\n",
    "            for w2 in word2:\n",
    "                if w2 not in indegree:\n",
    "                    indegree[w2] = 0\n",
    "\n",
    "            for w1, w2 in zip(word1, word2):\n",
    "                if w1 != w2:\n",
    "                    if w1 not in graph:\n",
    "                        graph[w1] = [w2]\n",
    "                    else:\n",
    "                        graph[w1].append(w2)\n",
    "                \n",
    "                    indegree[w2] += 1\n",
    "                    break\n",
    "            else: #else -> when for loop can execute normally (do not meet a break!!!)\n",
    "                if len(word2) < len(word1):\n",
    "                    return \"\"\n",
    "        \n",
    "        queue = deque()\n",
    "\n",
    "        ans = \"\"\n",
    "\n",
    "        for w, d in indegree.items():\n",
    "            if d == 0:\n",
    "                queue.append(w)\n",
    "        # print(queue)\n",
    "        # print(graph)\n",
    "        # print(indegree)\n",
    "        while queue:\n",
    "            \n",
    "            cur_w = queue.popleft()\n",
    "            ans += cur_w\n",
    "\n",
    "            if cur_w not in graph:\n",
    "                continue\n",
    "            for neighbour in graph[cur_w]:\n",
    "                indegree[neighbour] -= 1\n",
    "                if indegree[neighbour] == 0:\n",
    "                    queue.append(neighbour)\n",
    "        \n",
    "        return ans if len(ans) == len(indegree) else \"\"\n",
    "\n",
    "                    \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        adj_list = defaultdict(set)\n",
    "        in_degree = {c: 0 for word in words for c in word}\n",
    "    \n",
    "        for i in range(1, len(words)):\n",
    "            word1, word2 = words[i - 1], words[i]\n",
    "            for c1, c2 in zip(word1, word2):\n",
    "                if c1 != c2:\n",
    "                    if c2 not in adj_list[c1]:\n",
    "                        adj_list[c1].add(c2)\n",
    "                        in_degree[c2] += 1\n",
    "                    break\n",
    "            else:  # Check for cases like [\"abcd\", \"abc\"]\n",
    "                if len(word1) > len(word2):\n",
    "                    return \"\"\n",
    "    \n",
    "        # Step 2: Topological sort\n",
    "        output = []\n",
    "        queue = deque([c for c in in_degree if in_degree[c] == 0])\n",
    "        while queue:\n",
    "            c = queue.popleft()\n",
    "            output.append(c)\n",
    "            for next_c in adj_list[c]:\n",
    "                in_degree[next_c] -= 1\n",
    "                if in_degree[next_c] == 0:\n",
    "                    queue.append(next_c)\n",
    "    \n",
    "        # If not all letters have a position, return an empty string\n",
    "        if len(output) < len(in_degree):\n",
    "            return \"\"\n",
    "    \n",
    "        return ''.join(output)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        quene = collections.deque()\n",
    "        adj = [[] for _ in range(26)]\n",
    "        ind=[0] * 26\n",
    "        vis = set()\n",
    "\n",
    "        def saveadj(pre,cur):\n",
    "            if pre!=cur:\n",
    "                vis.add(ord(pre)-ord('a'))\n",
    "                vis.add(ord(cur)-ord('a')) \n",
    "                if (ord(cur)-ord('a')) not in adj[ord(pre)-ord('a')]:\n",
    "                    adj[ord(pre)-ord('a')].append(ord(cur)-ord('a'))\n",
    "                    ind[ord(cur)-ord('a')] += 1\n",
    "                return 1\n",
    "            else:\n",
    "                vis.add(ord(pre)-ord('a'))\n",
    "                return 0\n",
    "\n",
    "        for i in range(1,len(words)):\n",
    "            if len(words[i]) < len(words[i-1]) and words[i][:len(words[i])] == words[i-1][:len(words[i])]:\n",
    "                return ''\n",
    "            for j in range(min(len(words[i]),len(words[i-1]))):\n",
    "                if saveadj(words[i-1][j],words[i][j]):\n",
    "                    break\n",
    "\n",
    "\n",
    "        for word in words:\n",
    "            for i in range(1,len(word)):\n",
    "                if ord(word[i])-ord('a') not in vis:\n",
    "                    #print(i,word,(word[i-1],word[i]))\n",
    "                    saveadj(word[i-1],word[i])\n",
    "\n",
    "        for i in range(26):\n",
    "            # if ind[i]\n",
    "            if not ind[i] and i in vis:\n",
    "                quene.append(i)\n",
    "\n",
    "        print(adj)\n",
    "        print(ind)\n",
    "        print(quene)\n",
    "        ans = ''\n",
    "        \n",
    "        while quene:\n",
    "            cur = quene.popleft()\n",
    "            print(cur,chr(cur+ord('a')))\n",
    "            ans+=chr(cur+ord('a'))\n",
    "            for nex in adj[cur]:\n",
    "                ind[nex]-=1\n",
    "                if ind[nex] == 0:\n",
    "                    quene.append(nex) \n",
    "\n",
    "\n",
    "        if len(ans) == len(vis):\n",
    "            return ans\n",
    "        return ''   \n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        def diff(s1,s2):\n",
    "            n1,n2 = len(s1),len(s2)\n",
    "            i,j = 0,0\n",
    "            flag = False\n",
    "            while i<n1 and j<n2:\n",
    "                if not flag and s1[i]!=s2[j]:\n",
    "                    edges[ord(s1[i])-ord('a')].append(ord(s2[j])-ord('a'))\n",
    "                    deg[ord(s2[j])-ord('a')]+=1\n",
    "                    flag = True\n",
    "                else:\n",
    "                    if ord(s1[i])-ord('a') not in edges:\n",
    "                        edges[ord(s1[i])-ord('a')]=[]\n",
    "                    if ord(s2[j])-ord('a') not in edges:\n",
    "                        edges[ord(s2[j])-ord('a')]=[]\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "            if i==n1:\n",
    "                while j<n2:\n",
    "                    if ord(s2[j])-ord('a') not in edges:\n",
    "                        edges[ord(s2[j])-ord('a')]=[]\n",
    "                    j+=1\n",
    "            elif j==n2:\n",
    "                while i<n1:\n",
    "                    if ord(s1[i])-ord('a') not in edges:\n",
    "                        edges[ord(s1[i])-ord('a')]=[]\n",
    "                    i+=1\n",
    "            return\n",
    "\n",
    "\n",
    "        edges = collections.defaultdict(list)\n",
    "        deg = [0]*26\n",
    "        res = []\n",
    "\n",
    "        n = len(words)\n",
    "        if n==1:\n",
    "            return ''.join(list(set(words[0])))\n",
    "        for i in range(n-1):\n",
    "            if len(words[i+1])<len(words[i]) and words[i+1]==words[i][0:len(words[i+1])]:\n",
    "                return \"\"\n",
    "            diff(words[i],words[i+1])\n",
    "        q = collections.deque([u for u in range(26) if u in edges and deg[u]==0])\n",
    "        while q:\n",
    "            u = q.popleft()\n",
    "            res.append(chr(u+ord('a')))\n",
    "            for v in edges[u]:\n",
    "                deg[v]-=1\n",
    "                if deg[v]==0:\n",
    "                    q.append(v)\n",
    "        return ''.join(res) if len(res)==len(edges) else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        g=collections.defaultdict(list)\n",
    "        in_degree={c:0 for c in words[0]}\n",
    "        for s,t in itertools.pairwise(words):\n",
    "            for c in t:\n",
    "                in_degree.setdefault(c,0)      \n",
    "            for u,v in zip(s,t):\n",
    "                if u!=v:\n",
    "                    g[u].append(v)\n",
    "                    in_degree[v]+=1\n",
    "                    break\n",
    "            else:\n",
    "                if len(s)>len(t):\n",
    "                    return \"\"\n",
    "\n",
    "        q = [u for u, d in in_degree.items() if d == 0]\n",
    "        for u in q:\n",
    "            for v in g[u]:\n",
    "                in_degree[v] -= 1\n",
    "                if in_degree[v] == 0:\n",
    "                    q.append(v)\n",
    "        return ''.join(q) if len(q) == len(in_degree) else \"\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        graph = {}\n",
    "        word_set = set()\n",
    "        for i in range(len(words)-1):\n",
    "            if len(words[i]) > len(words[i+1]) and words[i][:len(words[i+1])] == words[i+1]:\n",
    "                return \"\" \n",
    "            for j in range(min(len(words[i]), len(words[i+1]))):\n",
    "                if words[i][j] != words[i+1][j]: \n",
    "                    if words[i][j] not in graph:\n",
    "                        graph[words[i][j]] = set()\n",
    "                    if words[i+1][j] not in graph[words[i][j]]:\n",
    "                        graph[words[i][j]].add(words[i+1][j])\n",
    "                    break\n",
    "               \n",
    "        \n",
    "        for i in range(len(words)):\n",
    "            for j in range(len(words[i])):\n",
    "                if words[i][j] not in word_set:\n",
    "                    word_set.add(words[i][j])\n",
    "        \n",
    "        visited = [False for _ in range(26)]\n",
    "        on_path = [False for _ in range(26)]\n",
    "        res = []\n",
    "        cycle = False\n",
    "\n",
    "        def topological_sort_util(v):\n",
    "            nonlocal cycle\n",
    "            if on_path[ord(v)-ord(\"a\")]:\n",
    "                cycle = True\n",
    "            if cycle or visited[ord(v)-ord(\"a\")]:\n",
    "                return\n",
    "            visited[ord(v)-ord(\"a\")], on_path[ord(v)-ord(\"a\")] = True, True\n",
    "            if v in graph:\n",
    "                for char in graph[v]:\n",
    "                    topological_sort_util(char)\n",
    "            res.append(v)\n",
    "            on_path[ord(v)-ord(\"a\")] = False\n",
    "\n",
    "        for char in graph:\n",
    "            topological_sort_util(char)\n",
    "\n",
    "        if cycle:\n",
    "            return \"\"\n",
    "        for char in word_set:\n",
    "            if char not in res:\n",
    "                res.append(char)\n",
    "        return \"\".join(res)[::-1]\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        edges = collections.defaultdict(list)\n",
    "        indegree = collections.defaultdict(int)\n",
    "        for i in range(len(words)):\n",
    "            for j in range(len(words[i])):\n",
    "                if words[i][j] not in indegree:\n",
    "                    indegree[words[i][j]] = 0\n",
    "        for i in range(1, len(words)):\n",
    "            l = min(len(words[i-1]), len(words[i]))\n",
    "            for j in range(l):\n",
    "                if words[i-1][j] != words[i][j]:\n",
    "                    edges[words[i-1][j]].append(words[i][j])\n",
    "                    indegree[words[i][j]] += 1\n",
    "                    break\n",
    "                if j == l - 1 and len(words[i-1]) > len(words[i]):\n",
    "                    return \"\"\n",
    "        q = [u for u in indegree.keys() if indegree[u] == 0]\n",
    "        res = \"\"\n",
    "        while q:\n",
    "            u = q.pop(0)\n",
    "            res += u\n",
    "            for v in edges[u]:\n",
    "                indegree[v] -= 1\n",
    "                if indegree[v] == 0:\n",
    "                    q.append(v)\n",
    "        return res if len(res) == len(indegree) else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "\n",
    "        adj = [set() for i in range(26)]\n",
    "        degree = [0] * 26\n",
    "        l = len(words)\n",
    "        memo = set()\n",
    "        for i in range(l):\n",
    "            for j in range(i + 1, l):\n",
    "                w1, w2 = words[i], words[j]\n",
    "                p = 0\n",
    "                while p < len(w1) and p < len(w2):\n",
    "                    if w1[p] == w2[p]:\n",
    "                        p += 1\n",
    "                    else:\n",
    "                        c1, c2 = w1[p], w2[p]\n",
    "                        if (c1, c2) not in memo:\n",
    "                            adj[ord(c1) - ord('a')].add(ord(c2) - ord('a')) \n",
    "                            degree[ord(c2) - ord('a')] += 1\n",
    "                            memo.add((c1, c2))\n",
    "                        break\n",
    "                if len(w1) > len(w2) and p == len(w2):\n",
    "                    return \"\"\n",
    "\n",
    "        q = deque()\n",
    "        vis = set()\n",
    "\n",
    "        for w in words:\n",
    "            for c in w:\n",
    "                vis.add(c)\n",
    "\n",
    "        for i in range(26):\n",
    "            if chr(i + ord('a')) not in vis:\n",
    "                pass\n",
    "            elif degree[i] == 0:\n",
    "                q.append(i)\n",
    "\n",
    "        ans = ''\n",
    "        while q:\n",
    "            cur = q.pop()\n",
    "            ans += chr(cur + ord('a'))\n",
    "            for nxt in adj[cur]:\n",
    "                degree[nxt] -= 1\n",
    "                if degree[nxt] == 0:\n",
    "                    q.append(nxt)\n",
    "        \n",
    "        return ans if len(ans) == len(vis) else \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        graph = self.build_graph(words)\n",
    "        if not graph:\n",
    "            return \"\"\n",
    "        return self.topological_sort(graph)\n",
    "\n",
    "    def build_graph(self, words):\n",
    "        graph = {}\n",
    "\n",
    "        for word in words:\n",
    "            for c in word:\n",
    "                if c not in graph:\n",
    "                    graph[c] = set()\n",
    "\n",
    "        n = len(words)\n",
    "        for i in range(n - 1):\n",
    "            for j in range(min(len(words[i]), len(words[i+1]))):\n",
    "                if words[i][j] != words[i+1][j]:\n",
    "                    graph[words[i][j]].add(words[i+1][j])\n",
    "                    break\n",
    "                if j == min(len(words[i]), len(words[i+1])) - 1:\n",
    "                    if len(words[i]) > len(words[i+1]):\n",
    "                        return None\n",
    "\n",
    "        return graph\n",
    "\n",
    "    def get_indegree(self, graph):\n",
    "        indegree = {c : 0 for c in graph}\n",
    "        for c in graph:\n",
    "            for neighbor in graph[c]:\n",
    "                indegree[neighbor] += 1\n",
    "\n",
    "        return indegree\n",
    "\n",
    "    def topological_sort(self, graph):\n",
    "        indegree = self.get_indegree(graph)\n",
    "        queue = [c for c in graph if indegree[c] == 0]\n",
    "        heapify(queue)\n",
    "\n",
    "        topo_order = \"\"\n",
    "        while queue:\n",
    "            c = heappop(queue)\n",
    "            topo_order += c\n",
    "            for neighbor in graph[c]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if indegree[neighbor] == 0:\n",
    "                    heappush(queue, neighbor)\n",
    "\n",
    "        return topo_order if len(topo_order) == len(graph) else \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val, sons, sonTrees):\n",
    "        self.val = val\n",
    "        self.sons = sons\n",
    "        self.sonTrees = sonTrees\n",
    "    \n",
    "    def __lt__(self, other):\n",
    "        return self.val < other.val\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        # 拓扑排序基础数据构造完成\n",
    "        T = {}\n",
    "        g = defaultdict(list)\n",
    "        S = [ [] for _ in range(100) ]\n",
    "        inDeg = defaultdict(int)\n",
    "        first = []\n",
    "        for w in words:\n",
    "            if first:\n",
    "                if first[-1] != w[0]:\n",
    "                    g[first[-1]].append(w[0])\n",
    "                    inDeg[w[0]] += 1\n",
    "                    if first[-1] not in inDeg:\n",
    "                        #print(\"first:\", first[-1])\n",
    "                        inDeg[first[-1]] = 0\n",
    "                    first.append(w[0])\n",
    "            else:\n",
    "                inDeg[w[0]] = 0\n",
    "                first.append(w[0])\n",
    "            if w[0] not in T:\n",
    "                T[w[0]] = Node(w[0], [], [])\n",
    "            t = T[w[0]]\n",
    "            for i in range(1, len(w)):\n",
    "                if w[i] in t.sons:\n",
    "                    k = t.sons.index(w[i])\n",
    "                    t = t.sonTrees[k]\n",
    "                else:\n",
    "                    if t.sons:\n",
    "                        g[t.sons[-1]].append(w[i])\n",
    "                        inDeg[w[i]] += 1\n",
    "                        if t.sons[-1] not in inDeg:\n",
    "                            #print(\"sons:\", t.sons[-1])\n",
    "                            inDeg[t.sons[-1]] = 0\n",
    "                    else:\n",
    "                        if w[i] not in inDeg:\n",
    "                            inDeg[w[i]] = 0\n",
    "                    t.sons.append(w[i])\n",
    "                    t.sonTrees.append(Node(w[i], [], []))\n",
    "                    t = t.sonTrees[-1]\n",
    "            if t.sons:\n",
    "                return \"\"\n",
    "                \n",
    "        # 进行拓扑排序\n",
    "        Q = deque([])\n",
    "        ST = []\n",
    "        NUM = len(inDeg)\n",
    "        #print(inDeg)\n",
    "        #print(g)\n",
    "        for k, v in inDeg.items():\n",
    "            if v == 0:\n",
    "                Q.append(k)\n",
    "        n = 0\n",
    "        while Q:\n",
    "            u = Q.popleft()\n",
    "            ST.append(u)\n",
    "            n += 1\n",
    "            for v in g[u]:\n",
    "                inDeg[v] -= 1\n",
    "                if inDeg[v] == 0:\n",
    "                    Q.append(v)\n",
    "        if n == NUM:\n",
    "            return \"\".join(ST)\n",
    "        else:\n",
    "            return \"\"\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        def diff(s1,s2):\n",
    "            n1,n2 = len(s1),len(s2)\n",
    "            i,j = 0,0\n",
    "            flag = False\n",
    "            while i<n1 and j<n2:\n",
    "                if not flag and s1[i]!=s2[j]:\n",
    "                    edges[ord(s1[i])-ord('a')].append(ord(s2[j])-ord('a'))\n",
    "                    deg[ord(s2[j])-ord('a')]+=1\n",
    "                    flag = True\n",
    "                else:\n",
    "                    if ord(s1[i])-ord('a') not in edges:\n",
    "                        edges[ord(s1[i])-ord('a')]=[]\n",
    "                    if ord(s2[j])-ord('a') not in edges:\n",
    "                        edges[ord(s2[j])-ord('a')]=[]\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "            if i==n1:\n",
    "                while j<n2:\n",
    "                    if ord(s2[j])-ord('a') not in edges:\n",
    "                        edges[ord(s2[j])-ord('a')]=[]\n",
    "                    j+=1\n",
    "            elif j==n2:\n",
    "                while i<n1:\n",
    "                    if ord(s1[i])-ord('a') not in edges:\n",
    "                        edges[ord(s1[i])-ord('a')]=[]\n",
    "                    i+=1\n",
    "            return\n",
    "\n",
    "\n",
    "        edges = collections.defaultdict(list)\n",
    "        deg = [0]*26\n",
    "        res = []\n",
    "\n",
    "        n = len(words)\n",
    "        if n==1:\n",
    "            return ''.join(list(set(words[0])))\n",
    "        for i in range(n-1):\n",
    "            if len(words[i+1])<len(words[i]) and words[i+1]==words[i][0:len(words[i+1])]:\n",
    "                return \"\"\n",
    "            diff(words[i],words[i+1])\n",
    "        q = collections.deque([u for u in range(26) if u in edges and deg[u]==0])\n",
    "        while q:\n",
    "            u = q.popleft()\n",
    "            res.append(chr(u+ord('a')))\n",
    "            for v in edges[u]:\n",
    "                deg[v]-=1\n",
    "                if deg[v]==0:\n",
    "                    q.append(v)\n",
    "        return ''.join(res) if len(res)==len(edges) else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        g = defaultdict(list)\n",
    "        inDeg = {c: 0 for c in words[0]}\n",
    "        for s, t in pairwise(words):\n",
    "            for c in t:\n",
    "                inDeg.setdefault(c, 0)\n",
    "            for u, v in zip(s, t):\n",
    "                if u != v:\n",
    "                    g[u].append(v)\n",
    "                    inDeg[v] += 1\n",
    "                    break\n",
    "            else:\n",
    "                if len(s) > len(t):\n",
    "                    return \"\"\n",
    "\n",
    "        q = [u for u, d in inDeg.items() if d == 0]\n",
    "        for u in q:\n",
    "            for v in g[u]:\n",
    "                inDeg[v] -= 1\n",
    "                if inDeg[v] == 0:\n",
    "                    q.append(v)\n",
    "        return ''.join(q) if len(q) == len(inDeg) else \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        g = defaultdict(list)\n",
    "        cnt = {c : 0 for c in words[0]}\n",
    "        for s, t in pairwise(words):\n",
    "            for c in t:\n",
    "                if c not in cnt.keys():\n",
    "                    cnt[c] = 0\n",
    "            for u, v in zip(s, t):\n",
    "                if u != v:\n",
    "                    g[u].append(v)\n",
    "                    cnt[v] += 1\n",
    "                    break\n",
    "            else:\n",
    "                if len(s) > len(t):\n",
    "                    return ''\n",
    "        \n",
    "        q = [u for u, d in cnt.items() if d == 0]\n",
    "        for u in q:\n",
    "            for v in g[u]:\n",
    "                cnt[v] -= 1\n",
    "                if cnt[v] == 0:\n",
    "                    q.append(v)\n",
    "        return ''.join(q) if len(q) == len(cnt) else ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        graph, s = defaultdict(list), set()\n",
    "        for w in words:\n",
    "            s = s.union(set(w))\n",
    "        d = [0] * 26\n",
    "        for a, b in pairwise(words):\n",
    "            for ca, cb in zip(a, b):\n",
    "                if ca != cb:\n",
    "                    graph[ca].append(cb)\n",
    "                    d[ord(cb) - ord('a')] += 1\n",
    "                    break\n",
    "            else: \n",
    "                if len(a) > len(b):\n",
    "                    return \"\"\n",
    "        start = [k for k in s if d[ord(k) - ord('a')] == 0]\n",
    "        for ch in start:\n",
    "            for nxt in graph[ch]:\n",
    "                d[v := ord(nxt) - ord('a')] -= 1\n",
    "                if not d[v]:\n",
    "                    start.append(nxt)\n",
    "        return \"\".join(start) if len(start) == len(s) else \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "\n",
    "\n",
    "        # # corner case:\n",
    "        # if len(words) == 1:\n",
    "        #     return words[0]\n",
    "        \n",
    "        # if len(words) == 0:\n",
    "        #     return \"\"\n",
    "\n",
    "        # word_set = set()\n",
    "        # for word in words:\n",
    "        #     for ch in word:\n",
    "        #         word_set.add(ch)\n",
    "\n",
    "        # n = len(word_set)\n",
    "        # g = defaultdict(list)\n",
    "        # #indegree = [0] * n\n",
    "        # # we need to use dict to save indegree\n",
    "        # indegree = {}\n",
    "        # for item in word_set:\n",
    "        #     indegree[item] = 0\n",
    "\n",
    "        # # generate dependency based on the word orders\n",
    "        # for w1, w2 in pairwise(words):\n",
    "\n",
    "        #     n1, n2 = len(w1), len(w2)\n",
    "        #     # return invalid cases\n",
    "        #     if n1 > n2:\n",
    "        #         if w1[:n2] == w1[:n2]: return \"\"\n",
    "\n",
    "        #     # all words are valid below\n",
    "        #     min_len = min(n1, n2)\n",
    "        #     for i in range(min_len):\n",
    "        #         if w1[i] != w2[i]: # only the first inequality matters\n",
    "        #             g[w1[i]].append(w2[i])\n",
    "        #             indegree[w2[i]] += 1\n",
    "        #             break\n",
    "        \n",
    "        # # q\n",
    "        # q = deque()\n",
    "        # for key, val in indegree.items():\n",
    "        #     if val == 0:\n",
    "        #         q.append(key)\n",
    "\n",
    "\n",
    "        indegree = {}\n",
    "\n",
    "        g = defaultdict(list)\n",
    "\n",
    "        word_set = set()\n",
    "\n",
    "        for w in words:\n",
    "            word_set = word_set.union(set(w))\n",
    "\n",
    "        # # populate g and indegree\n",
    "        # # \n",
    "        # for word in words:\n",
    "        #     for ch in word:\n",
    "        #         if ch not in indegree:\n",
    "        #             indegree[ch] = 0\n",
    "\n",
    "\n",
    "        for w1, w2 in pairwise(words):\n",
    "            n1, n2 = len(w1), len(w2)\n",
    "\n",
    "            if n1 > n2:\n",
    "                if w1[:n2] == w2: # invalid word that we cannot find order\n",
    "                    # g = defaultdict(list)\n",
    "                    # continue\n",
    "                    return \"\"\n",
    "                \n",
    "            min_n = min(n1, n2)\n",
    "\n",
    "\n",
    "            for i in range(min_n):\n",
    "                if w1[i] != w2[i]:\n",
    "                    g[w1[i]].append(w2[i]) # as w1 presents before w2\n",
    "                    break # we only need to make sure the first differene\n",
    "\n",
    "                    # else:\n",
    "                    # indegree[w2[i]] += 1\n",
    "\n",
    "        # def init_graph():\n",
    "        #     g, n = defaultdict(set), len(words)\n",
    "        #     for i in range(n - 1):\n",
    "        #         word0, word1 = words[i], words[i + 1]\n",
    "        #         n0, n1 = len(word0), len(word1)\n",
    "        #         # 形如[\"abc\", \"ab\"]的样例是违反定义的, 特殊判断\n",
    "        #         if n0 > n1 and word0[:n1] == word1:\n",
    "        #             return None\n",
    "                \n",
    "        #         m = min(n0, n1)\n",
    "        #         for j in range(m):\n",
    "        #             if word0[j] == word1[j]:\n",
    "        #                 continue\n",
    "        #             # 第一对不同的字符提供序关系, 后面的字符忽略\n",
    "        #             g[word0[j]].add(word1[j])\n",
    "        #             break\n",
    "        #     return g\n",
    "\n",
    "        # g = init_graph()\n",
    "        # if g is None:\n",
    "        #     return \"\"\n",
    "\n",
    "\n",
    "                    # break # only the first different letter matters\n",
    "            \n",
    "        def count_in_degree(g):\n",
    "            degree = {}\n",
    "            # 将出现字符的入度初始化为0\n",
    "            for word in words:\n",
    "                for ch in word:  \n",
    "                    degree[ch] = 0\n",
    "            \n",
    "            for char, charset in g.items():\n",
    "                for ch in charset:\n",
    "                    degree[ch] += 1\n",
    "            return degree\n",
    "\n",
    "        indegree = count_in_degree(g)\n",
    "        # populate q\n",
    "        q = deque()\n",
    "\n",
    "        for key in indegree.keys():\n",
    "            # letter = chr(i + ord('a'))\n",
    "            if indegree[key] == 0:\n",
    "                q.append(key)\n",
    "\n",
    "    \n",
    "\n",
    "        res = \"\"\n",
    "        # topo sort\n",
    "\n",
    "        while q:\n",
    "            cur_w = q.popleft()\n",
    "            res += cur_w\n",
    "            for child in g[cur_w]:\n",
    "                indegree[child] -= 1\n",
    "\n",
    "                if indegree[child] == 0:\n",
    "                    q.append(child)\n",
    "    \n",
    "\n",
    "\n",
    "        return res if len(res) == len(word_set) else \"\" # has to include all characters\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        indegree = {}\n",
    "\n",
    "        g = defaultdict(list)\n",
    "\n",
    "        s = set()\n",
    "\n",
    "        for w in words:\n",
    "            s = s.union(set(w))\n",
    "\n",
    "        # # populate g and indegree\n",
    "        # # \n",
    "        # for word in words:\n",
    "        #     for ch in word:\n",
    "        #         if ch not in indegree:\n",
    "        #             indegree[ch] = 0\n",
    "\n",
    "\n",
    "        for w1, w2 in pairwise(words):\n",
    "            n1, n2 = len(w1), len(w2)\n",
    "\n",
    "            if n1 > n2:\n",
    "                if w1[:n2] == w2: # invalid word that we cannot find order\n",
    "                    # g = defaultdict(list)\n",
    "                    # continue\n",
    "                    return \"\"\n",
    "                \n",
    "            min_n = min(n1, n2)\n",
    "\n",
    "\n",
    "            for i in range(min_n):\n",
    "                if w1[i] != w2[i]:\n",
    "                    g[w1[i]].append(w2[i]) # as w1 presents before w2\n",
    "                    break # we only need to make sure the first differene\n",
    "\n",
    "                    # else:\n",
    "                    # indegree[w2[i]] += 1\n",
    "\n",
    "        # def init_graph():\n",
    "        #     g, n = defaultdict(set), len(words)\n",
    "        #     for i in range(n - 1):\n",
    "        #         word0, word1 = words[i], words[i + 1]\n",
    "        #         n0, n1 = len(word0), len(word1)\n",
    "        #         # 形如[\"abc\", \"ab\"]的样例是违反定义的, 特殊判断\n",
    "        #         if n0 > n1 and word0[:n1] == word1:\n",
    "        #             return None\n",
    "                \n",
    "        #         m = min(n0, n1)\n",
    "        #         for j in range(m):\n",
    "        #             if word0[j] == word1[j]:\n",
    "        #                 continue\n",
    "        #             # 第一对不同的字符提供序关系, 后面的字符忽略\n",
    "        #             g[word0[j]].add(word1[j])\n",
    "        #             break\n",
    "        #     return g\n",
    "\n",
    "        # g = init_graph()\n",
    "        # if g is None:\n",
    "        #     return \"\"\n",
    "\n",
    "\n",
    "                    # break # only the first different letter matters\n",
    "            \n",
    "        def count_in_degree(g):\n",
    "            degree = {}\n",
    "            # 将出现字符的入度初始化为0\n",
    "            for word in words:\n",
    "                for ch in word:  \n",
    "                    degree[ch] = 0\n",
    "            \n",
    "            for char, charset in g.items():\n",
    "                for ch in charset:\n",
    "                    degree[ch] += 1\n",
    "            return degree\n",
    "\n",
    "        indegree = count_in_degree(g)\n",
    "        # populate q\n",
    "        q = deque()\n",
    "\n",
    "        for key in indegree.keys():\n",
    "            # letter = chr(i + ord('a'))\n",
    "            if indegree[key] == 0:\n",
    "                q.append(key)\n",
    "        res = []\n",
    "\n",
    "        \n",
    "\n",
    "        while q: # only has indegree=0 nodes\n",
    "\n",
    "            ch = q.popleft() # indegree=0 nodes ( no above parent)\n",
    "            res.append(ch)\n",
    "            for child in g[ch]:\n",
    "                indegree[child] -= 1 # as we removed ch, which is the parent for child\n",
    "                if indegree[child] == 0:\n",
    "                    # add to q as q has only nodes with indegree==0\n",
    "                    q.append(child)\n",
    "        \n",
    "        return ''.join(res) if len(res) == len(s) else \"\"# when q is empty, we finished all topo sort, all letters must be presented in the \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        def init_graph():\n",
    "            g, n = defaultdict(set), len(words)\n",
    "            for i in range(n - 1):\n",
    "                word0, word1 = words[i], words[i + 1]\n",
    "                n0, n1 = len(word0), len(word1)\n",
    "                # 形如[\"abc\", \"ab\"]的样例是违反定义的, 特殊判断\n",
    "                if n0 > n1 and word0[:n1] == word1:\n",
    "                    return None\n",
    "                \n",
    "                m = min(n0, n1)\n",
    "                for j in range(m):\n",
    "                    if word0[j] == word1[j]:\n",
    "                        continue\n",
    "                    # 第一对不同的字符提供序关系, 后面的字符忽略\n",
    "                    g[word0[j]].add(word1[j])\n",
    "                    break\n",
    "            return g\n",
    "        \n",
    "        def count_in_degree(g):\n",
    "            degree = {}\n",
    "            # 将出现字符的入度初始化为0\n",
    "            for word in words:\n",
    "                for ch in word:  \n",
    "                    degree[ch] = 0\n",
    "            \n",
    "            for char, charset in g.items():\n",
    "                for ch in charset:\n",
    "                    degree[ch] += 1\n",
    "            return degree\n",
    "        \n",
    "        g = init_graph()\n",
    "        if g is None:\n",
    "            return \"\"\n",
    "        in_degree = count_in_degree(g)\n",
    "        \n",
    "        queue, count = deque(), 0\n",
    "        for char, degree in in_degree.items():\n",
    "            count += 1\n",
    "            if degree == 0:\n",
    "                queue.append(char)\n",
    "            \n",
    "        order = \"\"\n",
    "        while queue:\n",
    "            ch = queue.popleft()\n",
    "            order += ch\n",
    "            \n",
    "            if ch in g:\n",
    "                for c in g[ch]:\n",
    "                    in_degree[c] -= 1\n",
    "                    if in_degree[c] == 0:\n",
    "                        queue.append(c)\n",
    "        print(order, count)\n",
    "        return order if len(order) == count else \"\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        m = len(words)\n",
    "        vas = set()\n",
    "        dct = defaultdict(set)\n",
    "        degree = defaultdict(set)\n",
    "        for i in range(m-1):\n",
    "            if words[i+1] == words[i][:len(words[i+1])] and len(words[i+1]) < len(words[i]):\n",
    "                return \"\"\n",
    "            for j in range(len(words[i])):\n",
    "                if words[i][j] != words[i+1][j]:\n",
    "                    dct[words[i][j]].add(words[i+1][j])\n",
    "                    degree[words[i+1][j]].add(words[i][j])\n",
    "                    break\n",
    "            vas = vas.union(set(list(words[i])))\n",
    "        vas = vas.union(set(list(words[m-1])))\n",
    "\n",
    "        ans = \"\"\n",
    "        stack = [w for w in vas if not degree[w]]\n",
    "        while stack:\n",
    "            ans += \"\".join(stack)\n",
    "            nex = []\n",
    "            for i in stack:\n",
    "                for j in dct[i]:\n",
    "                    degree[j].discard(i)\n",
    "                    if not degree[j]:\n",
    "                        nex.append(j)\n",
    "            stack = nex\n",
    "        return ans if len(ans) == len(vas) else \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "\n",
    "\n",
    "        # # corner case:\n",
    "        # if len(words) == 1:\n",
    "        #     return words[0]\n",
    "        \n",
    "        # if len(words) == 0:\n",
    "        #     return \"\"\n",
    "\n",
    "        # word_set = set()\n",
    "        # for word in words:\n",
    "        #     for ch in word:\n",
    "        #         word_set.add(ch)\n",
    "\n",
    "        # n = len(word_set)\n",
    "        # g = defaultdict(list)\n",
    "        # #indegree = [0] * n\n",
    "        # # we need to use dict to save indegree\n",
    "        # indegree = {}\n",
    "        # for item in word_set:\n",
    "        #     indegree[item] = 0\n",
    "\n",
    "        # # generate dependency based on the word orders\n",
    "        # for w1, w2 in pairwise(words):\n",
    "\n",
    "        #     n1, n2 = len(w1), len(w2)\n",
    "        #     # return invalid cases\n",
    "        #     if n1 > n2:\n",
    "        #         if w1[:n2] == w1[:n2]: return \"\"\n",
    "\n",
    "        #     # all words are valid below\n",
    "        #     min_len = min(n1, n2)\n",
    "        #     for i in range(min_len):\n",
    "        #         if w1[i] != w2[i]: # only the first inequality matters\n",
    "        #             g[w1[i]].append(w2[i])\n",
    "        #             indegree[w2[i]] += 1\n",
    "        #             break\n",
    "        \n",
    "        # # q\n",
    "        # q = deque()\n",
    "        # for key, val in indegree.items():\n",
    "        #     if val == 0:\n",
    "        #         q.append(key)\n",
    "\n",
    "    \n",
    "\n",
    "        # res = \"\"\n",
    "        # # topo sort\n",
    "\n",
    "        # while q:\n",
    "        #     cur_w = q.popleft()\n",
    "        #     res += cur_w\n",
    "        #     for child in g[cur_w]:\n",
    "        #         indegree[child] -= 1\n",
    "\n",
    "        #         if indegree[child] == 0:\n",
    "        #             q.append(child)\n",
    "    \n",
    "\n",
    "\n",
    "        # return res if len(res) == len(word_set) else \"\" # has to include all characters\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        indegree = {}\n",
    "\n",
    "        g = defaultdict(list)\n",
    "\n",
    "        s = set()\n",
    "\n",
    "        for w in words:\n",
    "            s = s.union(set(w))\n",
    "\n",
    "        # # populate g and indegree\n",
    "        # # \n",
    "        # for word in words:\n",
    "        #     for ch in word:\n",
    "        #         if ch not in indegree:\n",
    "        #             indegree[ch] = 0\n",
    "\n",
    "\n",
    "        for w1, w2 in pairwise(words):\n",
    "            n1, n2 = len(w1), len(w2)\n",
    "\n",
    "            if n1 > n2:\n",
    "                if w1[:n2] == w2: # invalid word that we cannot find order\n",
    "                    # g = defaultdict(list)\n",
    "                    # continue\n",
    "                    return \"\"\n",
    "                \n",
    "            min_n = min(n1, n2)\n",
    "\n",
    "\n",
    "            for i in range(min_n):\n",
    "                if w1[i] != w2[i]:\n",
    "                    g[w1[i]].append(w2[i]) # as w1 presents before w2\n",
    "                    break # we only need to make sure the first differene\n",
    "\n",
    "                    # else:\n",
    "                    # indegree[w2[i]] += 1\n",
    "\n",
    "        # def init_graph():\n",
    "        #     g, n = defaultdict(set), len(words)\n",
    "        #     for i in range(n - 1):\n",
    "        #         word0, word1 = words[i], words[i + 1]\n",
    "        #         n0, n1 = len(word0), len(word1)\n",
    "        #         # 形如[\"abc\", \"ab\"]的样例是违反定义的, 特殊判断\n",
    "        #         if n0 > n1 and word0[:n1] == word1:\n",
    "        #             return None\n",
    "                \n",
    "        #         m = min(n0, n1)\n",
    "        #         for j in range(m):\n",
    "        #             if word0[j] == word1[j]:\n",
    "        #                 continue\n",
    "        #             # 第一对不同的字符提供序关系, 后面的字符忽略\n",
    "        #             g[word0[j]].add(word1[j])\n",
    "        #             break\n",
    "        #     return g\n",
    "\n",
    "        # g = init_graph()\n",
    "        # if g is None:\n",
    "        #     return \"\"\n",
    "\n",
    "\n",
    "                    # break # only the first different letter matters\n",
    "            \n",
    "        def count_in_degree(g):\n",
    "            degree = {}\n",
    "            # 将出现字符的入度初始化为0\n",
    "            for word in words:\n",
    "                for ch in word:  \n",
    "                    degree[ch] = 0\n",
    "            \n",
    "            for char, charset in g.items():\n",
    "                for ch in charset:\n",
    "                    degree[ch] += 1\n",
    "            return degree\n",
    "\n",
    "        indegree = count_in_degree(g)\n",
    "        # populate q\n",
    "        q = deque()\n",
    "\n",
    "        for key in indegree.keys():\n",
    "            # letter = chr(i + ord('a'))\n",
    "            if indegree[key] == 0:\n",
    "                q.append(key)\n",
    "        res = []\n",
    "\n",
    "        \n",
    "\n",
    "        while q: # only has indegree=0 nodes\n",
    "\n",
    "            ch = q.popleft() # indegree=0 nodes ( no above parent)\n",
    "            res.append(ch)\n",
    "            for child in g[ch]:\n",
    "                indegree[child] -= 1 # as we removed ch, which is the parent for child\n",
    "                if indegree[child] == 0:\n",
    "                    # add to q as q has only nodes with indegree==0\n",
    "                    q.append(child)\n",
    "        \n",
    "        return ''.join(res) if len(res) == len(s) else \"\"# when q is empty, we finished all topo sort, all letters must be presented in the \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        def init_graph():\n",
    "            g, n = defaultdict(set), len(words)\n",
    "            for i in range(n - 1):\n",
    "                word0, word1 = words[i], words[i + 1]\n",
    "                n0, n1 = len(word0), len(word1)\n",
    "                # 形如[\"abc\", \"ab\"]的样例是违反定义的, 特殊判断\n",
    "                if n0 > n1 and word0[:n1] == word1:\n",
    "                    return None\n",
    "                \n",
    "                m = min(n0, n1)\n",
    "                for j in range(m):\n",
    "                    if word0[j] == word1[j]:\n",
    "                        continue\n",
    "                    # 第一对不同的字符提供序关系, 后面的字符忽略\n",
    "                    g[word0[j]].add(word1[j])\n",
    "                    break\n",
    "            return g\n",
    "        \n",
    "        def count_in_degree(g):\n",
    "            degree = {}\n",
    "            # 将出现字符的入度初始化为0\n",
    "            for word in words:\n",
    "                for ch in word:  \n",
    "                    degree[ch] = 0\n",
    "            \n",
    "            for char, charset in g.items():\n",
    "                for ch in charset:\n",
    "                    degree[ch] += 1\n",
    "            return degree\n",
    "        \n",
    "        g = init_graph()\n",
    "        if g is None:\n",
    "            return \"\"\n",
    "        in_degree = count_in_degree(g)\n",
    "        \n",
    "        queue, count = deque(), 0\n",
    "        for char, degree in in_degree.items():\n",
    "            count += 1\n",
    "            if degree == 0:\n",
    "                queue.append(char)\n",
    "            \n",
    "        order = \"\"\n",
    "        while queue:\n",
    "            ch = queue.popleft()\n",
    "            order += ch\n",
    "            \n",
    "            if ch in g:\n",
    "                for c in g[ch]:\n",
    "                    in_degree[c] -= 1\n",
    "                    if in_degree[c] == 0:\n",
    "                        queue.append(c)\n",
    "        print(order, count)\n",
    "        return order if len(order) == count else \"\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        \"\"\"\n",
    "        拓扑排序\n",
    "        \"\"\"\n",
    "        chars = set()\n",
    "        graph = collections.defaultdict(set)\n",
    "        indegrees = collections.defaultdict(int)\n",
    "        \n",
    "        chars.update(words[0])\n",
    "        for s, t in itertools.pairwise(words):\n",
    "            chars.update(t)\n",
    "            n = min(len(s), len(t))\n",
    "            for i in range(n):\n",
    "                if s[i] == t[i]:\n",
    "                    continue\n",
    "                if t[i] not in graph[s[i]]:\n",
    "                    indegrees[t[i]] += 1\n",
    "                    graph[s[i]].add(t[i])\n",
    "                break\n",
    "            else:\n",
    "                if len(s) > len(t):\n",
    "                    return ''\n",
    "\n",
    "        ret = ''\n",
    "\n",
    "        q = collections.deque()\n",
    "        for c in chars:\n",
    "            if indegrees[c] == 0:\n",
    "                q.append(c)\n",
    "        \n",
    "        while q:\n",
    "            c = q.popleft()\n",
    "            ret += c\n",
    "            for nc in graph[c]:\n",
    "                indegrees[nc] -= 1\n",
    "                if indegrees[nc] == 0:\n",
    "                    q.append(nc)\n",
    "    \n",
    "        return ret if len(ret) == len(chars) else ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "\n",
    "\n",
    "        \n",
    "        def init_graph():\n",
    "            g, n = defaultdict(set), len(words)\n",
    "            for i in range(n - 1):\n",
    "                word0, word1 = words[i], words[i + 1]\n",
    "                n0, n1 = len(word0), len(word1)\n",
    "                # 形如[\"abc\", \"ab\"]的样例是违反定义的, 特殊判断\n",
    "                if n0 > n1 and word0[:n1] == word1:\n",
    "                    return None\n",
    "                \n",
    "                m = min(n0, n1)\n",
    "                for j in range(m):\n",
    "                    if word0[j] == word1[j]:\n",
    "                        continue\n",
    "                    # 第一对不同的字符提供序关系, 后面的字符忽略\n",
    "                    g[word0[j]].add(word1[j])\n",
    "                    break\n",
    "            return g\n",
    "        \n",
    "        def count_in_degree(g):\n",
    "            degree = {}\n",
    "            # 将出现字符的入度初始化为0\n",
    "            for word in words:\n",
    "                for ch in word:  \n",
    "                    degree[ch] = 0\n",
    "            \n",
    "            for char, charset in g.items():\n",
    "                for ch in charset:\n",
    "                    degree[ch] += 1\n",
    "            return degree\n",
    "        \n",
    "        g = init_graph()\n",
    "        if g is None:\n",
    "            return \"\"\n",
    "        in_degree = count_in_degree(g)\n",
    "        \n",
    "        queue, count = deque(), 0\n",
    "        for char, degree in in_degree.items():\n",
    "            count += 1\n",
    "            if degree == 0:\n",
    "                queue.append(char)\n",
    "            \n",
    "        order = \"\"\n",
    "        while queue:\n",
    "            ch = queue.popleft()\n",
    "            order += ch\n",
    "            \n",
    "            if ch in g:\n",
    "                for c in g[ch]:\n",
    "                    in_degree[c] -= 1\n",
    "                    if in_degree[c] == 0:\n",
    "                        queue.append(c)\n",
    "        print(order, count)\n",
    "        return order if len(order) == count else \"\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        set_words = set(words)\n",
    "        if len(set_words) ==1 :\n",
    "            ans = set()\n",
    "            for i in set_words:\n",
    "                for ii in i:\n",
    "                    ans.add(ii)\n",
    "            return ''.join(ans)\n",
    "\n",
    "            #return set_words.pop()\n",
    "        # def init_graph() :\n",
    "        #     g,n = collections.defaultdict(set),len(words)\n",
    "        #     for i in range(n-1):\n",
    "        #         word0, word1 = words[i],words[i+1]\n",
    "        #         n0, n1 = len(word0), len(word1)\n",
    "                \n",
    "        #         if n0>n1 and word0[:n1] == word1: #行如 abc  ab 这样的例子是错误的需要单独进行判断\n",
    "        #             return None \n",
    "                \n",
    "        #         m = min(n0,n1)\n",
    "        #         for j in range(m):\n",
    "        #             if word0[j] == word1[j]:\n",
    "        #                 continue\n",
    "        #             g[word0[j]].add(word1[j])\n",
    "        #             break\n",
    "        #     return g\n",
    "        # g = init_graph()\n",
    "        # print(g)  \n",
    "#如果 相邻两个word 前面n 位 一样 n+1位，不一样 那么 n+1位的那个字母在前面\n",
    "#如果 相邻word 首字母不一样 ，在前面的首字母 在前 ==> 第一个不一样的字母在前\n",
    "        def init_relations():\n",
    "            n = len(words)\n",
    "            relations = collections.defaultdict(set) #这个题可以用set\n",
    "\n",
    "            for i in range(n-1):\n",
    "                word0,word1 = words[i],words[i+1]\n",
    "                n0, n1 = len(word0), len(word1)\n",
    "\n",
    "                if n0 > n1 and word0[:n1] == word1:\n",
    "                    return None\n",
    "                #!!! 取共同长度 作为搜索空间\n",
    "                search = min(n0,n1)\n",
    "\n",
    "                for k in range(search):\n",
    "                    if word0[k] == word1[k]:\n",
    "                        continue\n",
    "                    # elif word0[k] != word1[k]:\n",
    "                    relations[word0[k]].add(word1[k])\n",
    "                    break\n",
    "            return relations #python 注意函数最终返回值的层数，容易写在末尾的嵌套层数中 导致 输出结果发生变化\n",
    "        realtions = init_relations()\n",
    "        if  realtions is None :\n",
    "            return ''\n",
    "        print(realtions)\n",
    "        # print(g == realtions)\n",
    "        indegree = collections.defaultdict(int)\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            for ii in word:\n",
    "                indegree[ii]\n",
    "\n",
    "        for k,v in realtions.items():\n",
    "            #indegree[k] #在默认字典中 如果 不存在key = k 的键值对，那么直接在字典中添加，后序调用会返回其值\n",
    "            for i in v:\n",
    "                indegree[i] +=1\n",
    "        print(indegree)\n",
    "        #创建队列\n",
    "        que = collections.deque()\n",
    "        for x,y in indegree.items():\n",
    "            if y == 0:\n",
    "                que.append(x)\n",
    "        cnt = 0\n",
    "        while que:\n",
    "            curr = que.popleft()\n",
    "            ans.append(curr)\n",
    "            cnt +=1 \n",
    "\n",
    "            for s in realtions.keys():\n",
    "                if s == curr:\n",
    "                    for item in realtions[curr]:\n",
    "                        indegree[item] -=1\n",
    "                        if indegree[item] == 0 :\n",
    "                            que.append(item)\n",
    "        return ''.join(ans)  if cnt == len(indegree) else ''\n",
    "        #relation 也可能是空值 比如 \"wrt,wrtkj\"\n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        def init_graph():\n",
    "            g, n = defaultdict(set), len(words)\n",
    "            for i in range(n - 1):\n",
    "                word0, word1 = words[i], words[i + 1]\n",
    "                n0, n1 = len(word0), len(word1)\n",
    "                # 形如[\"abc\", \"ab\"]的样例是违反定义的, 特殊判断\n",
    "                if n0 > n1 and word0[:n1] == word1:\n",
    "                    return None\n",
    "                \n",
    "                m = min(n0, n1)\n",
    "                for j in range(m):\n",
    "                    if word0[j] == word1[j]:\n",
    "                        continue\n",
    "                    # 第一对不同的字符提供序关系, 后面的字符忽略\n",
    "                    g[word0[j]].add(word1[j])\n",
    "                    break\n",
    "            return g\n",
    "        \n",
    "        def count_in_degree(g):\n",
    "            degree = {}\n",
    "            # 将出现字符的入度初始化为0\n",
    "            for word in words:\n",
    "                for ch in word:  \n",
    "                    degree[ch] = 0\n",
    "            \n",
    "            for char, charset in g.items():\n",
    "                for ch in charset:\n",
    "                    degree[ch] += 1\n",
    "            return degree\n",
    "        \n",
    "        g = init_graph()\n",
    "        if g is None:\n",
    "            return \"\"\n",
    "        in_degree = count_in_degree(g)\n",
    "        \n",
    "        queue, count = deque(), 0\n",
    "        for char, degree in in_degree.items():\n",
    "            count += 1\n",
    "            if degree == 0:\n",
    "                queue.append(char)\n",
    "            \n",
    "        order = \"\"\n",
    "        while queue:\n",
    "            ch = queue.popleft()\n",
    "            order += ch\n",
    "            \n",
    "            if ch in g:\n",
    "                for c in g[ch]:\n",
    "                    in_degree[c] -= 1\n",
    "                    if in_degree[c] == 0:\n",
    "                        queue.append(c)\n",
    "        return order if len(order) == count else \"\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        graph = self.create_graph(words)\n",
    "        if not graph:\n",
    "            return \"\"\n",
    "        print(graph)\n",
    "        indegree = {i:0 for i in graph}\n",
    "        for k, v in graph.items():\n",
    "            for j in v:\n",
    "                indegree[j] += 1\n",
    "        print(indegree)\n",
    "        queue = collections.deque()\n",
    "        for k, v in indegree.items():\n",
    "            if v == 0:\n",
    "                queue.append(k)\n",
    "        \n",
    "        order = []\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            order.append(node)\n",
    "            for next_node in graph[node]:\n",
    "                indegree[next_node] -= 1\n",
    "                if indegree[next_node] == 0:\n",
    "                    queue.append(next_node)\n",
    "        if len(order) == len(graph):\n",
    "            return \"\".join(order)\n",
    "        return \"\"\n",
    "\n",
    "    def get_all_characters(self, words):\n",
    "        hashset = set()\n",
    "        for word in words:\n",
    "            for c in word:\n",
    "                hashset.add(c)\n",
    "        return hashset      \n",
    "\n",
    "    def create_graph(self, words):\n",
    "        all_characters = self.get_all_characters(words)\n",
    "        graph = {i:set() for i in all_characters}\n",
    "        for i in range(len(words) - 1):\n",
    "            word1 = words[i]\n",
    "            word2 = words[i + 1]\n",
    "            if not self.get_order(word1, word2, graph):\n",
    "                return None\n",
    "        return graph\n",
    "\n",
    "    def get_order(self, word1, word2, graph):\n",
    "        for i in range(min(len(word1), len(word2))):\n",
    "            if word1[i] != word2[i]:\n",
    "                graph[word1[i]].add(word2[i])\n",
    "                return True\n",
    "        if i < len(word1) - 1 and i == len(word2) - 1:    \n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        g = {}\n",
    "        for c in words[0]:\n",
    "            g[c] = []\n",
    "        for s, t in itertools.pairwise(words):\n",
    "            for c in t:\n",
    "                if c not in g:\n",
    "                    g[c] = []\n",
    "            for u, v in zip(s, t):\n",
    "                if u!=v:\n",
    "                    g[u].append(v)\n",
    "                    break\n",
    "\n",
    "            else:\n",
    "                if len(s) > len(t):\n",
    "                    return \"\"\n",
    "\n",
    "        VISITING, VISTIED = 1, 2\n",
    "        states = {}\n",
    "        order = []\n",
    "\n",
    "        def dfs(u):\n",
    "            states[u] = VISITING\n",
    "            for v in g[u]:\n",
    "                if v not in states:\n",
    "                    if not dfs(v):\n",
    "                        return False\n",
    "                elif states[v] == VISITING:\n",
    "                    return  False\n",
    "            order.append(u)\n",
    "            states[u] = VISTIED\n",
    "            return True\n",
    "\n",
    "        for u in g:\n",
    "            if u not in states:\n",
    "                if not dfs(u):\n",
    "                    return \"\"\n",
    "\n",
    "        return \"\".join(order[::-1])\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        def init_graph():\n",
    "            g,n=defaultdict(set), len(words)\n",
    "            for i in range(n-1):\n",
    "                word0,word1=words[i],words[i+1]\n",
    "                n0, n1 = len(word0),len(word1)\n",
    "                if n0>n1 and word0[:n1]==word1:\n",
    "                    return None\n",
    "                \n",
    "                m=min(n0,n1)\n",
    "                for j in range(m):\n",
    "                    if word0[j] ==word1[j]:\n",
    "                        continue\n",
    "                    g[word0[j]].add(word1[j])\n",
    "                    break\n",
    "            return g\n",
    "        def count_in_degree(g):\n",
    "            degree={}\n",
    "            for word in words:\n",
    "                for ch in word:\n",
    "                    degree[ch]=0\n",
    "            for char,charset in g.items():\n",
    "                for ch in charset:\n",
    "                    degree[ch]+=1\n",
    "            return degree\n",
    "        \n",
    "        g=init_graph()\n",
    "        if g is None:\n",
    "            return \"\"\n",
    "        in_degree =count_in_degree(g)\n",
    "\n",
    "        queue,count = deque(),0\n",
    "        for char, degree in in_degree.items():\n",
    "            count+=1\n",
    "            if degree==0:\n",
    "                queue.append(char)\n",
    "        order=\"\"\n",
    "        while queue:\n",
    "            ch=queue.popleft()\n",
    "            order +=ch\n",
    "            \n",
    "   \n",
    "            for c in g[ch]:\n",
    "                in_degree[c]-=1\n",
    "                if in_degree[c]==0:\n",
    "                    queue.append(c)\n",
    "        return order if len(order) == count else \"\"\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        # n = len(words)\n",
    "        # edges = []\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i+1,n):\n",
    "        #         idx = 0\n",
    "        #         w1 = words[i]\n",
    "        #         w2 = words[j]\n",
    "        #         l1 = len(w1)\n",
    "        #         l2 = len(w2)\n",
    "        #         while (idx < l1 and idx < l2) and w1[idx] == w2[idx]:\n",
    "        #             idx += 1\n",
    "                \n",
    "        #         if (idx < l1 and idx < l2):\n",
    "        #             if [w1[idx], w2[idx]] not in edges:\n",
    "        #                 edges.append([w1[idx], w2[idx]])\n",
    "\n",
    "        # # print(edges)\n",
    "        # dic = {}\n",
    "        # cc = 0\n",
    "        # graph = []\n",
    "        # for e in edges:\n",
    "        #     if e[0] not in dic:\n",
    "        #         dic[e[0]] = cc\n",
    "        #         cc += 1\n",
    "        #         graph.append([])\n",
    "        #     if e[1] not in dic:\n",
    "        #         dic[e[1]] = cc\n",
    "        #         cc += 1\n",
    "        #         graph.append([])\n",
    "\n",
    "        #     graph[dic[e[0]]].append(dic[e[1]])\n",
    "\n",
    "        # num_nodes = len(dic)\n",
    "        # indegree = [0] * n\n",
    "\n",
    "        # reverse_dic = {}\n",
    "        # for i in dic:\n",
    "        #     reverse_dic[dic[i]] = i\n",
    "\n",
    "        # for i in range(num_nodes):\n",
    "        #     for j in graph[i]:\n",
    "        #         indegree[j] += 1\n",
    "\n",
    "        # q = []\n",
    "        # for n in range(num_nodes):\n",
    "        #     if indegree[n] == 0:\n",
    "        #         q.append(n)\n",
    "\n",
    "        # cnt = 0\n",
    "        # ans = ''\n",
    "        # while q:\n",
    "        #     cur = q.pop(0)\n",
    "        #     cnt += 1\n",
    "        #     ans += reverse_dic[cur]\n",
    "\n",
    "        #     for nei in graph[cur]:\n",
    "        #         indegree[nei] -= 1\n",
    "\n",
    "        #         if indegree[nei] == 0:\n",
    "        #             q.append(nei)\n",
    "\n",
    "        # if cnt == num_nodes:\n",
    "        #     return ans\n",
    "        # else:\n",
    "        #     return ''   \n",
    "\n",
    "#####################################################\n",
    "     \n",
    "        # extract node and pair\n",
    "        self.flag = False \n",
    "        self.pairs = []\n",
    "        char = []\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i+1, len(words)):\n",
    "                self.get_pair(words[i], words[j])\n",
    "        # print(\"self.pairs:\", self.pairs)\n",
    "\n",
    "        if self.flag:\n",
    "            return ''\n",
    "\n",
    "        for i in range(len(words)):\n",
    "            for c in words[i]:\n",
    "                if c not in char:\n",
    "                    char.append(c)\n",
    "        \n",
    "        # build graph\n",
    "        g = {}\n",
    "        indegree = {}\n",
    "        for c in char:\n",
    "            # print(c)\n",
    "            g[c] = []\n",
    "            # print(g[c])\n",
    "            indegree[c] = 0\n",
    "        for pair in self.pairs:\n",
    "            # print(pair[0])\n",
    "            # print(\"g:\", g)\n",
    "            # print(g[pair[0]])\n",
    "            g[pair[0]].append(pair[1])\n",
    "            indegree[pair[1]] += 1\n",
    "        \n",
    "        # print(\"g:\", g)\n",
    "        q = list()\n",
    "        for c in char:\n",
    "            if indegree[c] == 0:\n",
    "                q.append(c)\n",
    "        \n",
    "        cnt = 0\n",
    "        seq = ''\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            for i in range(size):\n",
    "                c = q.pop(0)\n",
    "                cnt += 1\n",
    "                seq += c\n",
    "                for nb in g[c]:\n",
    "                    indegree[nb] -= 1\n",
    "                    if indegree[nb] == 0:\n",
    "                        q.append(nb)\n",
    "        \n",
    "        if cnt == len(char):\n",
    "            return seq\n",
    "        else:\n",
    "            return ''\n",
    "    \n",
    "    def get_pair(self, word1, word2):\n",
    "        n = min(len(word1), len(word2))\n",
    "        # print(\"word1:\",word1)\n",
    "        # print(\"word2:\",word2)\n",
    "        \n",
    "        for i in range(n):\n",
    "            if word1[i] != word2[i]:\n",
    "                if [word1[i], word2[i]] not in self.pairs:\n",
    "                    self.pairs.append([word1[i], word2[i]])\n",
    "                \n",
    "                break\n",
    "        \n",
    "        if word1[0:n] == word2[0:n] and len(word1) > len(word2):\n",
    "            # print(\"iii\")\n",
    "            self.flag =  True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        indegree = {}\n",
    "\n",
    "        g = defaultdict(list)\n",
    "\n",
    "        s = set()\n",
    "\n",
    "        for w in words:\n",
    "            s = s.union(set(w))\n",
    "\n",
    "        # # populate g and indegree\n",
    "        # # \n",
    "\n",
    "        # for w1, w2 in pairwise(words):\n",
    "        #     n1, n2 = len(w1), len(w2)\n",
    "\n",
    "        #     if n1 > n2:\n",
    "        #         if w1[:n2] == w2: # invalid word that we cannot find order\n",
    "        #             # g = defaultdict(list)\n",
    "        #             # continue\n",
    "        #             return \"\"\n",
    "                \n",
    "        #     min_n = min(n1, n2)\n",
    "\n",
    "        #     for word in words:\n",
    "        #         for ch in word:\n",
    "        #             if ch not in indegree:\n",
    "        #                 indegree[ch] = 0\n",
    "\n",
    "        #     for i in range(min_n):\n",
    "        #         if w1[i] != w2[i]:\n",
    "        #             g[w1[i]].append(w2[i]) # as w1 presents before w2\n",
    "\n",
    "        #             # else:\n",
    "        #             indegree[w2[i]] += 1\n",
    "\n",
    "        def init_graph():\n",
    "            g, n = defaultdict(set), len(words)\n",
    "            for i in range(n - 1):\n",
    "                word0, word1 = words[i], words[i + 1]\n",
    "                n0, n1 = len(word0), len(word1)\n",
    "                # 形如[\"abc\", \"ab\"]的样例是违反定义的, 特殊判断\n",
    "                if n0 > n1 and word0[:n1] == word1:\n",
    "                    return None\n",
    "                \n",
    "                m = min(n0, n1)\n",
    "                for j in range(m):\n",
    "                    if word0[j] == word1[j]:\n",
    "                        continue\n",
    "                    # 第一对不同的字符提供序关系, 后面的字符忽略\n",
    "                    g[word0[j]].add(word1[j])\n",
    "                    break\n",
    "            return g\n",
    "\n",
    "        g = init_graph()\n",
    "        if g is None:\n",
    "            return \"\"\n",
    "\n",
    "\n",
    "                    # break # only the first different letter matters\n",
    "            \n",
    "        def count_in_degree(g):\n",
    "            degree = {}\n",
    "            # 将出现字符的入度初始化为0\n",
    "            for word in words:\n",
    "                for ch in word:  \n",
    "                    degree[ch] = 0\n",
    "            \n",
    "            for char, charset in g.items():\n",
    "                for ch in charset:\n",
    "                    degree[ch] += 1\n",
    "            return degree\n",
    "\n",
    "        indegree = count_in_degree(g)\n",
    "        # populate q\n",
    "        q = deque()\n",
    "\n",
    "        for key in indegree.keys():\n",
    "            # letter = chr(i + ord('a'))\n",
    "            if indegree[key] == 0:\n",
    "                q.append(key)\n",
    "        res = []\n",
    "\n",
    "        \n",
    "\n",
    "        while q: # only has indegree=0 nodes\n",
    "\n",
    "            ch = q.popleft() # indegree=0 nodes ( no above parent)\n",
    "            res.append(ch)\n",
    "            for child in g[ch]:\n",
    "                indegree[child] -= 1 # as we removed ch, which is the parent for child\n",
    "                if indegree[child] == 0:\n",
    "                    # add to q as q has only nodes with indegree==0\n",
    "                    q.append(child)\n",
    "        \n",
    "        return ''.join(res) if len(res) == len(s) else \"\"# when q is empty, we finished all topo sort, all letters must be presented in the \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        def init_graph():\n",
    "            g, n = defaultdict(set), len(words)\n",
    "            for i in range(n - 1):\n",
    "                word0, word1 = words[i], words[i + 1]\n",
    "                n0, n1 = len(word0), len(word1)\n",
    "                # 形如[\"abc\", \"ab\"]的样例是违反定义的, 特殊判断\n",
    "                if n0 > n1 and word0[:n1] == word1:\n",
    "                    return None\n",
    "                \n",
    "                m = min(n0, n1)\n",
    "                for j in range(m):\n",
    "                    if word0[j] == word1[j]:\n",
    "                        continue\n",
    "                    # 第一对不同的字符提供序关系, 后面的字符忽略\n",
    "                    g[word0[j]].add(word1[j])\n",
    "                    break\n",
    "            return g\n",
    "        \n",
    "        def count_in_degree(g):\n",
    "            degree = {}\n",
    "            # 将出现字符的入度初始化为0\n",
    "            for word in words:\n",
    "                for ch in word:  \n",
    "                    degree[ch] = 0\n",
    "            \n",
    "            for char, charset in g.items():\n",
    "                for ch in charset:\n",
    "                    degree[ch] += 1\n",
    "            return degree\n",
    "        \n",
    "        g = init_graph()\n",
    "        if g is None:\n",
    "            return \"\"\n",
    "        in_degree = count_in_degree(g)\n",
    "        \n",
    "        queue, count = deque(), 0\n",
    "        for char, degree in in_degree.items():\n",
    "            count += 1\n",
    "            if degree == 0:\n",
    "                queue.append(char)\n",
    "            \n",
    "        order = \"\"\n",
    "        while queue:\n",
    "            ch = queue.popleft()\n",
    "            order += ch\n",
    "            \n",
    "            if ch in g:\n",
    "                for c in g[ch]:\n",
    "                    in_degree[c] -= 1\n",
    "                    if in_degree[c] == 0:\n",
    "                        queue.append(c)\n",
    "        print(order, count)\n",
    "        return order if len(order) == count else \"\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        graph = self.create_graph(words)\n",
    "        if not graph:\n",
    "            return \"\"\n",
    "        print(graph)\n",
    "        indegree = {i:0 for i in graph}\n",
    "        for k, v in graph.items():\n",
    "            for j in v:\n",
    "                indegree[j] += 1\n",
    "        print(indegree)\n",
    "        queue = collections.deque()\n",
    "        for k, v in indegree.items():\n",
    "            if v == 0:\n",
    "                queue.append(k)\n",
    "        \n",
    "        order = []\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            order.append(node)\n",
    "            for next_node in graph[node]:\n",
    "                indegree[next_node] -= 1\n",
    "                if indegree[next_node] == 0:\n",
    "                    queue.append(next_node)\n",
    "        if len(order) == len(graph):\n",
    "            return \"\".join(order)\n",
    "        return \"\"\n",
    "\n",
    "    def get_all_characters(self, words):\n",
    "        hashset = set()\n",
    "        for word in words:\n",
    "            for c in word:\n",
    "                hashset.add(c)\n",
    "        return hashset      \n",
    "\n",
    "    def create_graph(self, words):\n",
    "        all_characters = self.get_all_characters(words)\n",
    "        graph = {i:set() for i in all_characters}\n",
    "        for i in range(len(words) - 1):\n",
    "            word1 = words[i]\n",
    "            word2 = words[i + 1]\n",
    "            if not self.get_order(word1, word2, graph):\n",
    "                return None\n",
    "        return graph\n",
    "\n",
    "    def get_order(self, word1, word2, graph):\n",
    "        for i in range(min(len(word1), len(word2))):\n",
    "            if word1[i] == word2[i]:\n",
    "                continue\n",
    "            graph[word1[i]].add(word2[i])\n",
    "            return True\n",
    "        if len(word1) > len(word2):\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "            tot = set()\n",
    "            g = [set() for _ in range(26)]\n",
    "            deg_in = [0] * 26\n",
    "            for a, b in pairwise(words):\n",
    "                for ch in a:\n",
    "                    tot.add(ord(ch) - ord('a'))\n",
    "                if a == b or b.startswith(a):\n",
    "                    continue\n",
    "                if a.startswith(b):\n",
    "                    return ''\n",
    "                for pre, aft in zip(a, b):\n",
    "                    if pre == aft:\n",
    "                        continue\n",
    "                    if ord(pre) - ord('a') not in g[ord(aft) - ord('a')]:\n",
    "                        deg_in[ord(pre) - ord('a')] += 1\n",
    "                    g[ord(aft) - ord('a')].add(ord(pre) - ord('a'))\n",
    "                    break\n",
    "\n",
    "            for ch in words[-1]:\n",
    "                tot.add(ord(ch) - ord('a'))\n",
    "            dq = deque()\n",
    "            for i in tot:\n",
    "                if deg_in[i] == 0:\n",
    "                    dq.append(i)\n",
    "            ans = []\n",
    "            while dq:\n",
    "                a = dq.popleft()\n",
    "                ans.append(a)\n",
    "                for nxt in g[a]:\n",
    "                    deg_in[nxt] -= 1\n",
    "                    if deg_in[nxt] == 0:\n",
    "                        dq.append(nxt)\n",
    "            if sum(deg_in):\n",
    "                return ''\n",
    "            return ''.join(ascii_lowercase[i] for i in ans)[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import itertools\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        quene = collections.deque()\n",
    "        adj = [[] for _ in range(26)]\n",
    "        ind=[0] * 26\n",
    "        vis = set()\n",
    "\n",
    "\n",
    "        def saveadj(pre,cur):\n",
    "            if pre!=cur:\n",
    "                if (ord(cur)-ord('a')) not in adj[ord(pre)-ord('a')]:\n",
    "                    adj[ord(pre)-ord('a')].append(ord(cur)-ord('a'))\n",
    "                    ind[ord(cur)-ord('a')] += 1\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        for w in words:\n",
    "            vis.update(w)\n",
    "\n",
    "        for i,j in itertools.pairwise(words):\n",
    "            \n",
    "            for a,b in zip(i,j):\n",
    "                if saveadj(a,b):\n",
    "                    break\n",
    "            else:\n",
    "                if len(i) > len(j):\n",
    "                    return ''\n",
    "\n",
    "\n",
    "        # for word in words:\n",
    "        #     for i in range(1,len(word)):\n",
    "        #         if ord(word[i])-ord('a') not in vis:\n",
    "        #             #print(i,word,(word[i-1],word[i]))\n",
    "        #             saveadj(word[i-1],word[i])\n",
    "\n",
    "\n",
    "\n",
    "        for i in range(26):\n",
    "            # if ind[i]\n",
    "            if not ind[i] and chr(i+ord('a')) in vis:\n",
    "                quene.append(i)\n",
    "\n",
    "\n",
    "        # print(ind,adj,vis)\n",
    "        # print(list(zip('abc','qwer')))\n",
    "        ans = ''\n",
    "        \n",
    "        while quene:\n",
    "            cur = quene.popleft()\n",
    "            print(cur,chr(cur+ord('a')))\n",
    "            ans+=chr(cur+ord('a'))\n",
    "            for nex in adj[cur]:\n",
    "                ind[nex]-=1\n",
    "                if ind[nex] == 0:\n",
    "                    quene.append(nex) \n",
    "\n",
    "\n",
    "        if len(ans) == len(vis):\n",
    "            return ans\n",
    "        return ''   \n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        \n",
    "        childs = {}\n",
    "        for word in words:\n",
    "            for a in word:\n",
    "                childs[a] = set()\n",
    "        if len(childs) == 1:\n",
    "            return words[0][0]\n",
    "        self.flag = False\n",
    "        def findchild(words, nowi):\n",
    "            # print(words, nowi)\n",
    "            if len(words) <= 1:\n",
    "                return \n",
    "            if nowi >= len(words[0]):\n",
    "                findchild(words[1:], nowi + 1)\n",
    "                return \n",
    "\n",
    "            start = 0\n",
    "            first = words[0][nowi]\n",
    "            for i in range(1, len(words)):\n",
    "                if nowi >= len(words[i]):\n",
    "                    self.flag = True\n",
    "                    return\n",
    "                if words[i][nowi] != first:\n",
    "                    # print(first, '->',words[i][nowi] )\n",
    "                    findchild(words[start:i], nowi + 1)\n",
    "                    # print('end')\n",
    "                    childs[first].add(words[i][nowi])\n",
    "                    first = words[i][nowi]\n",
    "                    start = i\n",
    "\n",
    "            findchild(words[start:], nowi + 1)\n",
    "\n",
    "        findchild(words, 0)\n",
    "        if self.flag:\n",
    "            return ''\n",
    "        \n",
    "        dads = {}\n",
    "        for child in childs:\n",
    "            for dad in childs[child]:\n",
    "                if dad not in dads:\n",
    "                    dads[dad] = set()\n",
    "                dads[dad].add(child)\n",
    "\n",
    "        ans = []\n",
    "        de = deque([a for a in childs if a not in dads])\n",
    "        while de:\n",
    "            for _ in range(len(de)):\n",
    "                t = de.pop()\n",
    "                ans.append(t)\n",
    "                for child in childs[t]:\n",
    "                    dads[child] -= {t, }\n",
    "                    if not dads[child]:\n",
    "                        de.append(child)\n",
    "        if len(ans) != len(childs):\n",
    "            return ''\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        s=set()\n",
    "        for w in words:\n",
    "            s=s|set(w)\n",
    "        ind=collections.defaultdict(int)\n",
    "        ad=collections.defaultdict(list)\n",
    "        n=len(words)\n",
    "       \n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                a=words[i]\n",
    "                b=words[j]\n",
    "                if a==b:\n",
    "                    continue\n",
    "                f=0\n",
    "                for k in range(min(len(a),len(b))):\n",
    "                    ca=a[k]\n",
    "                    cb=b[k]\n",
    "                    if ca!=cb:\n",
    "                        f=1\n",
    "                        ind[cb]+=1\n",
    "                        ad[ca].append(cb)\n",
    "                        break\n",
    "                if f==0:\n",
    "                    if len(a)>len(b):\n",
    "                        return \"\"\n",
    "        stack=collections.deque()\n",
    "    \n",
    "        for x in s:\n",
    "            if ind[x]==0:\n",
    "                stack.append(x)\n",
    "        ans=[]\n",
    "  \n",
    "        while stack:\n",
    "            cur=stack.popleft()\n",
    "            ans.append(cur)\n",
    "            for nex in ad[cur]:\n",
    "                ind[nex]-=1\n",
    "                if ind[nex]==0:\n",
    "                    stack.append(nex)\n",
    "        if len(ans)!=len(s):\n",
    "            return \"\"\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_relation(s1: str, s2: str) -> tuple:\n",
    "    for i in range(min(s1.__len__(), s2.__len__())):\n",
    "        if s1[i] != s2[i]:\n",
    "            return s1[i], s2[i]\n",
    "    else:\n",
    "        if s1.__len__() > s2.__len__():\n",
    "            raise IOError\n",
    "    return None, None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        all_letters = set()\n",
    "        visited_dict = dict()\n",
    "        for w in words:\n",
    "            for l in w:\n",
    "                all_letters.add(l)\n",
    "                visited_dict[l] = False\n",
    "        all_letters = list(all_letters)\n",
    "\n",
    "        no_pre = all_letters.copy()\n",
    "        adj_dict = dict()\n",
    "\n",
    "        def check_circle(start: int) -> bool:\n",
    "            q = deque([start])\n",
    "            count = 0\n",
    "            while q:\n",
    "                current = q.popleft()\n",
    "                if start == current:\n",
    "                    count += 1\n",
    "                    if count == 2:\n",
    "                        return True\n",
    "                try:\n",
    "                    q.extend(adj_dict[current])\n",
    "                except KeyError:\n",
    "                    pass\n",
    "            return False\n",
    "\n",
    "        pre_word = words[0]\n",
    "        for index, word in enumerate(words[1:]):\n",
    "            try:\n",
    "                small, big = get_relation(pre_word, word)\n",
    "            except IOError:\n",
    "                print(\"Invalid pattern\", word, \">\", pre_word)\n",
    "                return ''\n",
    "            if small and big:\n",
    "                try:\n",
    "                    adj_dict[small].append(big)\n",
    "                except KeyError:\n",
    "                    adj_dict[small] = [big]\n",
    "                if check_circle(small):  # have circle\n",
    "                    print(\"have circle at node\", big)\n",
    "                    return ''\n",
    "                try:\n",
    "                    no_pre.remove(big)\n",
    "                except ValueError:\n",
    "                    pass\n",
    "                pre_word = word\n",
    "        ans = ''\n",
    "        q = deque(no_pre)\n",
    "        while q:\n",
    "            current = q.popleft()\n",
    "            ans += current\n",
    "            visited_dict[current] = True\n",
    "            try:\n",
    "                for item in adj_dict[current]:\n",
    "                    if not visited_dict[item]:\n",
    "                        visited_dict[item] = True\n",
    "                        q.append(item)\n",
    "            except KeyError:\n",
    "                pass\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "\n",
    "\n",
    "        # # corner case:\n",
    "        # if len(words) == 1:\n",
    "        #     return words[0]\n",
    "        \n",
    "        # if len(words) == 0:\n",
    "        #     return \"\"\n",
    "\n",
    "        # word_set = set()\n",
    "        # for word in words:\n",
    "        #     for ch in word:\n",
    "        #         word_set.add(ch)\n",
    "\n",
    "        # n = len(word_set)\n",
    "        # g = defaultdict(list)\n",
    "        # #indegree = [0] * n\n",
    "        # # we need to use dict to save indegree\n",
    "        # indegree = {}\n",
    "        # for item in word_set:\n",
    "        #     indegree[item] = 0\n",
    "\n",
    "        # # generate dependency based on the word orders\n",
    "        # for w1, w2 in pairwise(words):\n",
    "\n",
    "        #     n1, n2 = len(w1), len(w2)\n",
    "        #     # return invalid cases\n",
    "        #     if n1 > n2:\n",
    "        #         if w1[:n2] == w1[:n2]: return \"\"\n",
    "\n",
    "        #     # all words are valid below\n",
    "        #     min_len = min(n1, n2)\n",
    "        #     for i in range(min_len):\n",
    "        #         if w1[i] != w2[i]: # only the first inequality matters\n",
    "        #             g[w1[i]].append(w2[i])\n",
    "        #             indegree[w2[i]] += 1\n",
    "        #             break\n",
    "        \n",
    "        # # q\n",
    "        # q = deque()\n",
    "        # for key, val in indegree.items():\n",
    "        #     if val == 0:\n",
    "        #         q.append(key)\n",
    "\n",
    "\n",
    "        indegree = {}\n",
    "\n",
    "        g = defaultdict(list)\n",
    "\n",
    "        word_set = set()\n",
    "\n",
    "        for w in words:\n",
    "            word_set = word_set.union(set(w))\n",
    "\n",
    "        # # populate g and indegree\n",
    "        # # \n",
    "        # for word in words:\n",
    "        #     for ch in word:\n",
    "        #         if ch not in indegree:\n",
    "        #             indegree[ch] = 0\n",
    "\n",
    "\n",
    "        for w1, w2 in pairwise(words):\n",
    "            n1, n2 = len(w1), len(w2)\n",
    "\n",
    "            if n1 > n2:\n",
    "                if w1[:n2] == w2: # invalid word that we cannot find order\n",
    "                    # g = defaultdict(list)\n",
    "                    # continue\n",
    "                    return \"\"\n",
    "                \n",
    "            min_n = min(n1, n2)\n",
    "\n",
    "\n",
    "            for i in range(min_n):\n",
    "                if w1[i] != w2[i]:\n",
    "                    g[w1[i]].append(w2[i]) # as w1 presents before w2\n",
    "                    break # we only need to make sure the first differene\n",
    "\n",
    "                    # else:\n",
    "                    # indegree[w2[i]] += 1\n",
    "\n",
    "        # def init_graph():\n",
    "        #     g, n = defaultdict(set), len(words)\n",
    "        #     for i in range(n - 1):\n",
    "        #         word0, word1 = words[i], words[i + 1]\n",
    "        #         n0, n1 = len(word0), len(word1)\n",
    "        #         # 形如[\"abc\", \"ab\"]的样例是违反定义的, 特殊判断\n",
    "        #         if n0 > n1 and word0[:n1] == word1:\n",
    "        #             return None\n",
    "                \n",
    "        #         m = min(n0, n1)\n",
    "        #         for j in range(m):\n",
    "        #             if word0[j] == word1[j]:\n",
    "        #                 continue\n",
    "        #             # 第一对不同的字符提供序关系, 后面的字符忽略\n",
    "        #             g[word0[j]].add(word1[j])\n",
    "        #             break\n",
    "        #     return g\n",
    "\n",
    "        # g = init_graph()\n",
    "        # if g is None:\n",
    "        #     return \"\"\n",
    "\n",
    "\n",
    "                    # break # only the first different letter matters\n",
    "            \n",
    "        def count_in_degree(g):\n",
    "            degree = {}\n",
    "            # 将出现字符的入度初始化为0\n",
    "            for word in words:\n",
    "                for ch in word:  \n",
    "                    degree[ch] = 0\n",
    "            \n",
    "            for char, charset in g.items():\n",
    "                for ch in charset:\n",
    "                    degree[ch] += 1\n",
    "            return degree\n",
    "\n",
    "        indegree = count_in_degree(g)\n",
    "        # populate q\n",
    "        q = deque()\n",
    "\n",
    "        for key, val in indegree.items():\n",
    "            # letter = chr(i + ord('a'))\n",
    "            if val == 0:\n",
    "                q.append(key)\n",
    "\n",
    "    \n",
    "\n",
    "        res = \"\"\n",
    "        # topo sort\n",
    "\n",
    "        while q:\n",
    "            cur_w = q.popleft()\n",
    "            res += cur_w\n",
    "            for child in g[cur_w]:\n",
    "                indegree[child] -= 1\n",
    "\n",
    "                if indegree[child] == 0:\n",
    "                    q.append(child)\n",
    "    \n",
    "\n",
    "\n",
    "        return res if len(res) == len(word_set) else \"\" # has to include all characters\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        indegree = {}\n",
    "\n",
    "        g = defaultdict(list)\n",
    "\n",
    "        s = set()\n",
    "\n",
    "        for w in words:\n",
    "            s = s.union(set(w))\n",
    "\n",
    "        # # populate g and indegree\n",
    "        # # \n",
    "        # for word in words:\n",
    "        #     for ch in word:\n",
    "        #         if ch not in indegree:\n",
    "        #             indegree[ch] = 0\n",
    "\n",
    "\n",
    "        for w1, w2 in pairwise(words):\n",
    "            n1, n2 = len(w1), len(w2)\n",
    "\n",
    "            if n1 > n2:\n",
    "                if w1[:n2] == w2: # invalid word that we cannot find order\n",
    "                    # g = defaultdict(list)\n",
    "                    # continue\n",
    "                    return \"\"\n",
    "                \n",
    "            min_n = min(n1, n2)\n",
    "\n",
    "\n",
    "            for i in range(min_n):\n",
    "                if w1[i] != w2[i]:\n",
    "                    g[w1[i]].append(w2[i]) # as w1 presents before w2\n",
    "                    break # we only need to make sure the first differene\n",
    "\n",
    "                    # else:\n",
    "                    # indegree[w2[i]] += 1\n",
    "\n",
    "        # def init_graph():\n",
    "        #     g, n = defaultdict(set), len(words)\n",
    "        #     for i in range(n - 1):\n",
    "        #         word0, word1 = words[i], words[i + 1]\n",
    "        #         n0, n1 = len(word0), len(word1)\n",
    "        #         # 形如[\"abc\", \"ab\"]的样例是违反定义的, 特殊判断\n",
    "        #         if n0 > n1 and word0[:n1] == word1:\n",
    "        #             return None\n",
    "                \n",
    "        #         m = min(n0, n1)\n",
    "        #         for j in range(m):\n",
    "        #             if word0[j] == word1[j]:\n",
    "        #                 continue\n",
    "        #             # 第一对不同的字符提供序关系, 后面的字符忽略\n",
    "        #             g[word0[j]].add(word1[j])\n",
    "        #             break\n",
    "        #     return g\n",
    "\n",
    "        # g = init_graph()\n",
    "        # if g is None:\n",
    "        #     return \"\"\n",
    "\n",
    "\n",
    "                    # break # only the first different letter matters\n",
    "            \n",
    "        def count_in_degree(g):\n",
    "            degree = {}\n",
    "            # 将出现字符的入度初始化为0\n",
    "            for word in words:\n",
    "                for ch in word:  \n",
    "                    degree[ch] = 0\n",
    "            \n",
    "            for char, charset in g.items():\n",
    "                for ch in charset:\n",
    "                    degree[ch] += 1\n",
    "            return degree\n",
    "\n",
    "        indegree = count_in_degree(g)\n",
    "        # populate q\n",
    "        q = deque()\n",
    "\n",
    "        for key in indegree.keys():\n",
    "            # letter = chr(i + ord('a'))\n",
    "            if indegree[key] == 0:\n",
    "                q.append(key)\n",
    "        res = []\n",
    "\n",
    "        \n",
    "\n",
    "        while q: # only has indegree=0 nodes\n",
    "\n",
    "            ch = q.popleft() # indegree=0 nodes ( no above parent)\n",
    "            res.append(ch)\n",
    "            for child in g[ch]:\n",
    "                indegree[child] -= 1 # as we removed ch, which is the parent for child\n",
    "                if indegree[child] == 0:\n",
    "                    # add to q as q has only nodes with indegree==0\n",
    "                    q.append(child)\n",
    "        \n",
    "        return ''.join(res) if len(res) == len(s) else \"\"# when q is empty, we finished all topo sort, all letters must be presented in the \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        def init_graph():\n",
    "            g, n = defaultdict(set), len(words)\n",
    "            for i in range(n - 1):\n",
    "                word0, word1 = words[i], words[i + 1]\n",
    "                n0, n1 = len(word0), len(word1)\n",
    "                # 形如[\"abc\", \"ab\"]的样例是违反定义的, 特殊判断\n",
    "                if n0 > n1 and word0[:n1] == word1:\n",
    "                    return None\n",
    "                \n",
    "                m = min(n0, n1)\n",
    "                for j in range(m):\n",
    "                    if word0[j] == word1[j]:\n",
    "                        continue\n",
    "                    # 第一对不同的字符提供序关系, 后面的字符忽略\n",
    "                    g[word0[j]].add(word1[j])\n",
    "                    break\n",
    "            return g\n",
    "        \n",
    "        def count_in_degree(g):\n",
    "            degree = {}\n",
    "            # 将出现字符的入度初始化为0\n",
    "            for word in words:\n",
    "                for ch in word:  \n",
    "                    degree[ch] = 0\n",
    "            \n",
    "            for char, charset in g.items():\n",
    "                for ch in charset:\n",
    "                    degree[ch] += 1\n",
    "            return degree\n",
    "        \n",
    "        g = init_graph()\n",
    "        if g is None:\n",
    "            return \"\"\n",
    "        in_degree = count_in_degree(g)\n",
    "        \n",
    "        queue, count = deque(), 0\n",
    "        for char, degree in in_degree.items():\n",
    "            count += 1\n",
    "            if degree == 0:\n",
    "                queue.append(char)\n",
    "            \n",
    "        order = \"\"\n",
    "        while queue:\n",
    "            ch = queue.popleft()\n",
    "            order += ch\n",
    "            \n",
    "            if ch in g:\n",
    "                for c in g[ch]:\n",
    "                    in_degree[c] -= 1\n",
    "                    if in_degree[c] == 0:\n",
    "                        queue.append(c)\n",
    "        print(order, count)\n",
    "        return order if len(order) == count else \"\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        hash = defaultdict(list)\n",
    "        nums = [0] *26\n",
    "        vis = set()\n",
    "        for word in words:\n",
    "            for i in word:\n",
    "                vis.add(i)\n",
    "        for i in range(1,len(words)):\n",
    "            j = 0\n",
    "            while j<min(len(words[i]),len(words[i-1])) and words[i][j] == words[i-1][j]:\n",
    "                j+=1\n",
    "            if j == len(words[i]) and j<len(words[i-1]):\n",
    "                return \"\"\n",
    "            if j<min(len(words[i]),len(words[i-1])):\n",
    "                hash[words[i-1][j]].append(words[i][j])\n",
    "                nums[ord(words[i][j]) - ord('a')]+=1\n",
    "        # print(hash,nums)\n",
    "        que = []\n",
    "        ans = \"\"\n",
    "        for i in range(26):\n",
    "            if chr(i+ord('a')) in vis and nums[i] == 0:\n",
    "                que.append(chr(i+ord('a')))\n",
    "        print(que,hash)\n",
    "        while que:\n",
    "            curr = []\n",
    "            for q in que:\n",
    "                ans += q\n",
    "                for i in hash[q]:\n",
    "                    nums[ord(i)-ord('a')]-=1\n",
    "                    if nums[ord(i)-ord('a')] == 0:\n",
    "                        curr.append(i)\n",
    "            que = curr\n",
    "        if len(ans) != len(vis):\n",
    "            return \"\"\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        graph = defaultdict(list)\n",
    "        letters = {c for word in words for c in word}\n",
    "        for i in range(len(words)-1):\n",
    "            prefixSame = True\n",
    "            for x, y in zip(words[i], words[i+1]):\n",
    "                if x != y:\n",
    "                    prefixSame = False\n",
    "                    graph[x].append(y)\n",
    "                    break\n",
    "            if prefixSame and len(words[i]) > len(words[i+1]):\n",
    "                return \"\"\n",
    "        visited = defaultdict(int)\n",
    "        for c in letters:\n",
    "            visited[c] = -1\n",
    "        valid = True\n",
    "        path = []\n",
    "        def dfs(node):\n",
    "            nonlocal valid\n",
    "            if not valid or visited[node] == 1:\n",
    "                return\n",
    "            if visited[node] == 0:\n",
    "                valid = False\n",
    "                return\n",
    "            visited[node] = 0\n",
    "            for nxt in graph[node]:\n",
    "                dfs(nxt)\n",
    "            path.append(node)\n",
    "            visited[node] = 1\n",
    "        for c in letters:\n",
    "            dfs(c)\n",
    "        return (\"\").join(path[::-1]) if valid else \"\"\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        # 构建字符集\n",
    "        n_words = len(words)\n",
    "        postorder = defaultdict(list)\n",
    "        \n",
    "        for i in range(n_words-1):\n",
    "            a = words[i]\n",
    "            b = words[i+1]\n",
    "            len_max = max(len(a), len(b))\n",
    "            for j in range(len_max):\n",
    "                if j ==  len(b): # a长\n",
    "                    return \"\"\n",
    "                elif j == len(a):# b长\n",
    "                    break # 下一组\n",
    "                elif a[j] != b[j]:\n",
    "                    postorder[a[j]].append(b[j])\n",
    "                    break\n",
    "        vis = [False] * 26\n",
    "        on_path = [False] * 26 \n",
    "        path = []\n",
    "        has_cycle = False \n",
    "        def dfs(graph, c):\n",
    "            idx = ord(c) - ord('a')\n",
    "            nonlocal has_cycle\n",
    "            \n",
    "            if on_path[idx]:\n",
    "                has_cycle = True\n",
    "            if has_cycle or vis[idx]:\n",
    "                return \n",
    "            on_path[idx] = True \n",
    "            vis[idx] = True\n",
    "            for nxt_c in postorder[c]:\n",
    "                dfs(graph, nxt_c)\n",
    "            path.append(c)\n",
    "            on_path[idx] = False \n",
    "        char_set = set()\n",
    "        for i in range(n_words):\n",
    "            for c in words[i]:\n",
    "                char_set.add(c)\n",
    "        keyset = set( postorder.keys())\n",
    "        for c in keyset:\n",
    "            dfs(postorder,c)\n",
    "\n",
    "        if has_cycle:\n",
    "            return \"\"\n",
    "        path_already = set(path)\n",
    "        for  c in char_set:\n",
    "            if c not in path_already:\n",
    "                path.append(c)\n",
    "        return \"\".join(path[::-1])\n",
    "\n",
    "                \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "\n",
    "\n",
    "        # corner case:\n",
    "        # if len(words) == 1:\n",
    "        #     return words[0]\n",
    "        \n",
    "        # if len(words) == 0:\n",
    "        #     return \"\"\n",
    "\n",
    "        word_set = set()\n",
    "        for word in words:\n",
    "            for ch in word:\n",
    "                word_set.add(ch)\n",
    "\n",
    "        # n = len(word_set)\n",
    "        # g = defaultdict(list)\n",
    "        # #indegree = [0] * n\n",
    "        # # we need to use dict to save indegree\n",
    "        # indegree = {}\n",
    "        # for item in word_set:\n",
    "        #     indegree[item] = 0\n",
    "\n",
    "        # # generate dependency based on the word orders\n",
    "        # for w1, w2 in pairwise(words):\n",
    "\n",
    "        #     n1, n2 = len(w1), len(w2)\n",
    "        #     # return invalid cases\n",
    "        #     if n1 > n2:\n",
    "        #         if w1[:n2] == w1[:n2]: return \"\"\n",
    "\n",
    "        #     # all words are valid below\n",
    "        #     min_len = min(n1, n2)\n",
    "        #     for i in range(min_len):\n",
    "        #         if w1[i] != w2[i]: # only the first inequality matters\n",
    "        #             g[w1[i]].append(w2[i])\n",
    "        #             indegree[w2[i]] += 1\n",
    "        #             break\n",
    "        \n",
    "        # # q\n",
    "        # q = deque()\n",
    "        # for key, val in indegree.items():\n",
    "        #     if val == 0:\n",
    "        #         q.append(key)\n",
    "\n",
    "\n",
    "        indegree = {}\n",
    "\n",
    "        g = defaultdict(list)\n",
    "\n",
    "        # word_set = set()\n",
    "\n",
    "        # for w in words:\n",
    "        #     word_set = word_set.union(set(w))\n",
    "\n",
    "        # populate g and indegree\n",
    "        # \n",
    "        for ch in word_set:\n",
    "            if ch not in indegree:\n",
    "                indegree[ch] = 0\n",
    "\n",
    "\n",
    "        for w1, w2 in pairwise(words):\n",
    "            n1, n2 = len(w1), len(w2)\n",
    "\n",
    "            if n1 > n2:\n",
    "                if w1[:n2] == w2: # invalid word that we cannot find order\n",
    "                    # g = defaultdict(list)\n",
    "                    # continue\n",
    "                    return \"\"\n",
    "                \n",
    "            min_n = min(n1, n2)\n",
    "\n",
    "\n",
    "            for i in range(min_n):\n",
    "                if w1[i] != w2[i]:\n",
    "                    g[w1[i]].append(w2[i]) # as w1 presents before w2\n",
    "                    indegree[w2[i]]+=1\n",
    "                    break # we only need to make sure the first differene\n",
    "\n",
    "        # indegree = {}\n",
    "        # # 将出现字符的入度初始化为0\n",
    "        # for word in words:\n",
    "        #     for ch in word:  \n",
    "        #         indegree[ch] = 0\n",
    "        \n",
    "        # for char, charset in g.items():\n",
    "        #     for ch in charset:\n",
    "        #         indegree[ch] += 1\n",
    "\n",
    "                    # else:\n",
    "                    # indegree[w2[i]] += 1\n",
    "\n",
    "        # def init_graph():\n",
    "        #     g, n = defaultdict(set), len(words)\n",
    "        #     for i in range(n - 1):\n",
    "        #         word0, word1 = words[i], words[i + 1]\n",
    "        #         n0, n1 = len(word0), len(word1)\n",
    "        #         # 形如[\"abc\", \"ab\"]的样例是违反定义的, 特殊判断\n",
    "        #         if n0 > n1 and word0[:n1] == word1:\n",
    "        #             return None\n",
    "                \n",
    "        #         m = min(n0, n1)\n",
    "        #         for j in range(m):\n",
    "        #             if word0[j] == word1[j]:\n",
    "        #                 continue\n",
    "        #             # 第一对不同的字符提供序关系, 后面的字符忽略\n",
    "        #             g[word0[j]].add(word1[j])\n",
    "        #             break\n",
    "        #     return g\n",
    "\n",
    "        # g = init_graph()\n",
    "        # if g is None:\n",
    "        #     return \"\"\n",
    "\n",
    "\n",
    "                    # break # only the first different letter matters\n",
    "            \n",
    "        \n",
    "        # populate q\n",
    "        q = deque()\n",
    "\n",
    "        for key, val in indegree.items():\n",
    "            # letter = chr(i + ord('a'))\n",
    "            if val == 0:\n",
    "                q.append(key)\n",
    "\n",
    "    \n",
    "\n",
    "        res = \"\"\n",
    "        # topo sort\n",
    "\n",
    "        while q:\n",
    "            cur_w = q.popleft()\n",
    "            res += cur_w\n",
    "            for child in g[cur_w]:\n",
    "                indegree[child] -= 1\n",
    "\n",
    "                if indegree[child] == 0:\n",
    "                    q.append(child)\n",
    "    \n",
    "\n",
    "\n",
    "        return res if len(res) == len(word_set) else \"\" # has to include all characters\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        indegree = {}\n",
    "\n",
    "        g = defaultdict(list)\n",
    "\n",
    "        s = set()\n",
    "\n",
    "        for w in words:\n",
    "            s = s.union(set(w))\n",
    "\n",
    "        # # populate g and indegree\n",
    "        # # \n",
    "        # for word in words:\n",
    "        #     for ch in word:\n",
    "        #         if ch not in indegree:\n",
    "        #             indegree[ch] = 0\n",
    "\n",
    "\n",
    "        for w1, w2 in pairwise(words):\n",
    "            n1, n2 = len(w1), len(w2)\n",
    "\n",
    "            if n1 > n2:\n",
    "                if w1[:n2] == w2: # invalid word that we cannot find order\n",
    "                    # g = defaultdict(list)\n",
    "                    # continue\n",
    "                    return \"\"\n",
    "                \n",
    "            min_n = min(n1, n2)\n",
    "\n",
    "\n",
    "            for i in range(min_n):\n",
    "                if w1[i] != w2[i]:\n",
    "                    g[w1[i]].append(w2[i]) # as w1 presents before w2\n",
    "                    break # we only need to make sure the first differene\n",
    "\n",
    "                    # else:\n",
    "                    # indegree[w2[i]] += 1\n",
    "\n",
    "        # def init_graph():\n",
    "        #     g, n = defaultdict(set), len(words)\n",
    "        #     for i in range(n - 1):\n",
    "        #         word0, word1 = words[i], words[i + 1]\n",
    "        #         n0, n1 = len(word0), len(word1)\n",
    "        #         # 形如[\"abc\", \"ab\"]的样例是违反定义的, 特殊判断\n",
    "        #         if n0 > n1 and word0[:n1] == word1:\n",
    "        #             return None\n",
    "                \n",
    "        #         m = min(n0, n1)\n",
    "        #         for j in range(m):\n",
    "        #             if word0[j] == word1[j]:\n",
    "        #                 continue\n",
    "        #             # 第一对不同的字符提供序关系, 后面的字符忽略\n",
    "        #             g[word0[j]].add(word1[j])\n",
    "        #             break\n",
    "        #     return g\n",
    "\n",
    "        # g = init_graph()\n",
    "        # if g is None:\n",
    "        #     return \"\"\n",
    "\n",
    "\n",
    "                    # break # only the first different letter matters\n",
    "            \n",
    "        def count_in_degree(g):\n",
    "            degree = {}\n",
    "            # 将出现字符的入度初始化为0\n",
    "            for word in words:\n",
    "                for ch in word:  \n",
    "                    degree[ch] = 0\n",
    "            \n",
    "            for char, charset in g.items():\n",
    "                for ch in charset:\n",
    "                    degree[ch] += 1\n",
    "            return degree\n",
    "\n",
    "        indegree = count_in_degree(g)\n",
    "        # populate q\n",
    "        q = deque()\n",
    "\n",
    "        for key in indegree.keys():\n",
    "            # letter = chr(i + ord('a'))\n",
    "            if indegree[key] == 0:\n",
    "                q.append(key)\n",
    "        res = []\n",
    "\n",
    "        \n",
    "\n",
    "        while q: # only has indegree=0 nodes\n",
    "\n",
    "            ch = q.popleft() # indegree=0 nodes ( no above parent)\n",
    "            res.append(ch)\n",
    "            for child in g[ch]:\n",
    "                indegree[child] -= 1 # as we removed ch, which is the parent for child\n",
    "                if indegree[child] == 0:\n",
    "                    # add to q as q has only nodes with indegree==0\n",
    "                    q.append(child)\n",
    "        \n",
    "        return ''.join(res) if len(res) == len(s) else \"\"# when q is empty, we finished all topo sort, all letters must be presented in the \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        def init_graph():\n",
    "            g, n = defaultdict(set), len(words)\n",
    "            for i in range(n - 1):\n",
    "                word0, word1 = words[i], words[i + 1]\n",
    "                n0, n1 = len(word0), len(word1)\n",
    "                # 形如[\"abc\", \"ab\"]的样例是违反定义的, 特殊判断\n",
    "                if n0 > n1 and word0[:n1] == word1:\n",
    "                    return None\n",
    "                \n",
    "                m = min(n0, n1)\n",
    "                for j in range(m):\n",
    "                    if word0[j] == word1[j]:\n",
    "                        continue\n",
    "                    # 第一对不同的字符提供序关系, 后面的字符忽略\n",
    "                    g[word0[j]].add(word1[j])\n",
    "                    break\n",
    "            return g\n",
    "        \n",
    "        def count_in_degree(g):\n",
    "            degree = {}\n",
    "            # 将出现字符的入度初始化为0\n",
    "            for word in words:\n",
    "                for ch in word:  \n",
    "                    degree[ch] = 0\n",
    "            \n",
    "            for char, charset in g.items():\n",
    "                for ch in charset:\n",
    "                    degree[ch] += 1\n",
    "            return degree\n",
    "        \n",
    "        g = init_graph()\n",
    "        if g is None:\n",
    "            return \"\"\n",
    "        in_degree = count_in_degree(g)\n",
    "        \n",
    "        queue, count = deque(), 0\n",
    "        for char, degree in in_degree.items():\n",
    "            count += 1\n",
    "            if degree == 0:\n",
    "                queue.append(char)\n",
    "            \n",
    "        order = \"\"\n",
    "        while queue:\n",
    "            ch = queue.popleft()\n",
    "            order += ch\n",
    "            \n",
    "            if ch in g:\n",
    "                for c in g[ch]:\n",
    "                    in_degree[c] -= 1\n",
    "                    if in_degree[c] == 0:\n",
    "                        queue.append(c)\n",
    "        print(order, count)\n",
    "        return order if len(order) == count else \"\"\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
